Arbres B+ et Arbres LSM sont deux structures de données de base lorsque nous parlons des éléments constitutifs de Bases de données. Les arbres B+ sont utilisés lorsque nous avons besoin de moins de temps de recherche et d'insertion et, d'un autre côté, les arbres LSM sont utilisés lorsque nous avons des ensembles de données gourmands en écriture et que les lectures ne sont pas si élevées.

Cet article enseignera Arbre de fusion structuré de journaux alias Arbre LSM . Les arbres LSM constituent la structure de données sous-jacente à de nombreuses bases de données de type clé-valeur distribuées NoSQL hautement évolutives, telles que DynamoDB, Cassandra et ScyllaDB d'Amazon.

Arbres LSM

Une version simple des arbres LSM comprend 2 niveaux de structure de données arborescente :

• Mémorisable et réside entièrement en mémoire (disons T0)
• SStables stockées sur le disque (disons T1)

Arbre LSM simple

De nouveaux enregistrements sont insérés dans le composant mémable T0. Si l'insertion fait dépasser un certain seuil de taille au composant T0, un segment contigu d'entrées est supprimé de T0 et fusionné dans T1 sur le disque.

Flux de travail LSM

LSM utilise principalement 3 concepts pour optimiser les opérations de lecture et d'écriture :

• Table de chaînes triées (SSTables) : Les données sont triées dans l'ordre de tri de sorte que chaque fois que les données sont lues, leur complexité temporelle sera O( Log(N) ) dans le pire des cas, où N est le nombre d'entrées dans une table de base de données.

  1. SSTable

• Mémorisable :
  • Une structure en mémoire
  • Stocke les données de manière triée
  • Agit comme un cache de réécriture
  • Après avoir atteint une certaine taille, ses données sont vidées en tant que SSTable vers la base de données
  • Au fur et à mesure, le nombre de SSTable augmente sur le disque, et si une clé n'est pas présente dans les enregistrements
    • Lors de la lecture de cette clé, nous devons lire toutes les SSTables, ce qui augmente la complexité du temps de lecture.
    • Pour surmonter ce problème, le filtre Bloom entre en scène.
    • Le filtre Bloom est une structure de données peu encombrante qui peut nous indiquer si la clé est manquante dans nos enregistrements avec un taux de précision de 99,9 %.
    • Pour utiliser ce filtre, nous pouvons y ajouter nos entrées lors de leur écriture, et vérifier la clé au début des requêtes de lecture afin de répondre plus efficacement aux requêtes lorsqu'elles arrivent en première place.

Représentation mémorisable

• Compactage :
  • Comme nous stockons les données sous forme de SSTable sur le disque, disons qu'il y a N SSTable et la taille de chaque table est M
  • Alors le pire des cas Lire la complexité temporelle est O( N* Journal(M) )
  • Ainsi, à mesure que le nombre de SSTables augmente, Lire la complexité temporelle augmente également.
  • De plus, lorsque nous vidons simplement les SSTables dans la base de données, la même clé est présente dans plusieurs SSTables.
  • Voici l'utilisation d'un compacteur
  • Compactor s'exécute en arrière-plan, fusionne les SSTables et supprime plusieurs lignes avec les mêmes, ajoute la nouvelle clé avec les dernières données et les stocke dans un nouveau SSTable fusionné/compacté.

3.1. SSTables vidées sur le disque

3.6. Compacteur compacté 2 SSTables à 1 SSTable

Conclusion:

• Les écritures sont stockées dans une arborescence en mémoire (Memtable). Toutes les structures de données de support (filtres Bloom et index clairsemé) sont également mises à jour si nécessaire.
• Lorsque cette arborescence devient trop grande, elle est vidée sur le disque avec les clés dans un ordre trié.
• Lorsqu'une lecture arrive, nous la vérifions à l'aide du filtre Bloom. Si le filtre Bloom indique que la valeur n'est pas présente, nous indiquons au client que la clé est introuvable. Si le filtre bloom signifie que la valeur est présente, nous commençons à itérer les SSTables du plus récent au plus ancien.
• Complexités temporelles du LSM
  • Temps de lecture: O(log(N)) où N est le nombre d'enregistrements sur le disque
  • Temps d'écriture : O(1) comme il l'écrit en mémoire
  • Supprimer l'heure : O(log(N)) où N est le nombre d'enregistrements sur le disque
• Les arbres LSM peuvent être modifiés pour créer des structures de données plus efficaces en utilisant plus de 2 filtres. Certains d'entre eux sont bLSM, Diff-Index LSM.