B+ Arbres i Arbres LSM són dues estructures de dades bàsiques quan parlem dels blocs de construcció Bases de dades. Els arbres B+ s'utilitzen quan necessitem menys temps de cerca i inserció i, d'altra banda, els arbres LSM s'utilitzen quan tenim conjunts de dades intensius en escriptura i les lectures no són tan altes.

Aquest article ensenyarà sobre Arbre de fusió estructurat de registre aka Arbre LSM . Els arbres LSM són l'estructura de dades subjacent a moltes bases de dades de tipus clau-valor distribuïdes NoSQL altament escalables, com ara DynamoDB, Cassandra i ScyllaDB d'Amazon.

Arbres LSM

Una versió senzilla de LSM Trees inclou 2 nivells d'estructura de dades semblant a un arbre:

• Memtable i resideix completament a la memòria (diguem que T0)
• SStables emmagatzemats al disc (diguem T1)

Arbre LSM simple

Els nous registres s'insereixen al component T0 memtable. Si la inserció fa que el component T0 superi un determinat llindar de mida, un segment contigu d'entrades s'elimina de T0 i es fusiona amb T1 al disc.

Flux de treball de LSM

LSM utilitza principalment 3 conceptes per optimitzar les operacions de lectura i escriptura:

• Taula de cadenes ordenades (SSTables) : Les dades s'ordenen en ordre ordenat de manera que sempre que es llegeixin les dades, la seva complexitat temporal serà O( Log(N) ) en el pitjor dels casos, on N és el nombre d'entrades en una taula de base de dades.

  1. SSTable

• Memtable :
  • Una estructura en memòria
  • Emmagatzema les dades de manera ordenada
  • Actua com a memòria cau de reescriptura
  • Després d'arribar a una mida determinada, les seves dades s'envien com a SSTable a la base de dades
  • Com, el nombre de SSTable augmenta al disc, i si alguna clau no està present als registres
    • Mentre llegim aquesta clau, hem de llegir totes les SSTables, la qual cosa augmenta la complexitat del temps de lectura.
    • Per solucionar aquest problema, el filtre Bloom entra a la imatge.
    • El filtre Bloom és una estructura de dades eficient en l'espai que ens pot indicar si falta la clau als nostres registres amb una taxa de precisió del 99,9%.
    • Per utilitzar aquest filtre, podem afegir-hi les nostres entrades quan s'escriuen i comprovar la clau al principi de les sol·licituds de lectura per tal de servir les sol·licituds de manera més eficient quan arribin en primer lloc.

Representació memorable

• Compactació :
  • Com que estem emmagatzemant dades com a SSTable al disc, diguem que n'hi ha N SSTable i la mida de cada taula és M
  • Aleshores el pitjor dels casos Llegeix la complexitat temporal és O( N* Registre (M) )
  • Així, a mesura que augmenta el nombre de SSTables, el La complexitat del temps de lectura també augmenta.
  • A més, quan estem netejant els SSTables a la base de dades, la mateixa clau està present a diversos SSTables
  • Aquí ve l'ús d'un compactador
  • Compactor s'executa en segon pla, fusiona SSTables i elimina diverses files amb el mateix i afegeix la nova clau amb les dades més recents i les emmagatzema en un nou SSTable combinat/compactat.

3.1. SSTables enviat al disc

3.6. El compactador va compactar 2 SSTables a 1 SSTable

Conclusió:

• Les escriptures s'emmagatzemen en un arbre a la memòria (Memtable). Les estructures de dades de suport (filtres de floració i índex escàs) també s'actualitzen si cal.
• Quan aquest arbre es fa massa gran, s'envia al disc amb les claus ordenades.
• Quan arriba una lectura, la comprovem amb el filtre de floració. Si el filtre de floració indica que el valor no és present, diem al client que no s'ha pogut trobar la clau. Si el filtre de floració significa que el valor és present, comencem a iterar SSTables del més nou al més antic.
• Complexitats temporals de LSM
  • Hora de lectura: O(log(N)) on N és el nombre de registres del disc
  • Hora d'escriptura: O(1) tal com escriu a la memòria
  • Hora de supressió: O(log(N)) on N és el nombre de registres del disc
• Els arbres LSM es poden modificar a estructures de dades més eficients mitjançant més de 2 filtres. Alguns d'ells són bLSM, Diff-Index LSM.