B+ Copaci și Arborii LSM sunt două structuri de date de bază atunci când vorbim despre elementele de bază ale Baze de date. Arborii B+ sunt folosiți atunci când avem nevoie de mai puțin timp de căutare și inserare și, pe de altă parte, arborii LSM sunt folosiți atunci când avem seturi de date cu multă scriere și citirile nu sunt atât de mari.

Acest articol va învăța despre Arborele de îmbinare structurat în jurnal aka Arborele LSM . Arborii LSM sunt structura de date care stă la baza multor baze de date de tip cheie-valoare distribuite NoSQL, cum ar fi DynamoDB, Cassandra și ScyllaDB de la Amazon.

Arborii LSM

O versiune simplă a LSM Trees cuprinde 2 niveluri de structură de date arborescentă:

• Memorabil și rezidă complet în memorie (să spunem T0)
• SStables stocate pe disc (să spunem T1)

Arborele LSM simplu

Înregistrările noi sunt inserate în componenta T0 memtable. Dacă inserarea face ca componenta T0 să depășească un anumit prag de dimensiune, un segment contiguu de intrări este eliminat din T0 și fuzionat în T1 pe disc.

Flux de lucru LSM

LSM utilizează în principal 3 concepte pentru a optimiza operațiunile de citire și scriere:

• Tabel de șiruri sortate (SSTables) : Datele sunt sortate în ordine astfel încât, ori de câte ori sunt citite datele, complexitatea lor temporală va fi O( Log(N) ) în cel mai rău caz, unde N este numărul de intrări dintr-un tabel de bază de date.

  1. SSTable

• Memtable :
  • O structură în memorie
  • Stochează datele într-un mod sortat
  • Acționează ca un cache de rescriere
  • După atingerea unei anumite dimensiuni, datele sale sunt eliminate ca SSTable în baza de date
  • Așa cum, numărul de SSTable crește în Disk și dacă o cheie nu este prezentă în înregistrări
    • În timp ce citim cheia, trebuie să citim toate SSTables, ceea ce crește complexitatea timpului de citire.
    • Pentru a depăși această problemă, filtrul Bloom intră în imagine.
    • Filtrul Bloom este o structură de date eficientă din punct de vedere al spațiului, care ne poate spune dacă cheia lipsește în înregistrările noastre cu o rată de precizie de 99,9%.
    • Pentru a folosi acest filtru, putem adăuga intrările noastre atunci când sunt scrise și putem verifica cheia la începutul solicitărilor de citire pentru a servi cererile mai eficient atunci când acestea vin pe primul loc.

Reprezentare memorabilă

• Compactare :
  • Pe măsură ce stocăm date ca SSTable pe disc, să presupunem că există N SSTable și dimensiunea fiecărui tabel este M
  • Atunci cel mai rău caz Citit complexitatea timpului este O( N* Jurnal(M) )
  • Deci, pe măsură ce numărul de SSTable crește, Complexitatea timpului de citire crește de asemenea.
  • De asemenea, atunci când doar spălăm SSTables în baza de date, aceeași cheie este prezentă în mai multe SSTables
  • Aici vine utilizarea unui compactor
  • Compactor rulează în fundal, îmbină SSTable și elimină mai multe rânduri cu același și adaugă noua cheie cu cele mai recente date și le stochează într-un nou SSTable îmbinat/compactat.

3.1. SSTables șterse pe disc

3.6. Compactorul a compactat 2 SSTtable la 1 SSTable

Concluzie:

• Scrierile sunt stocate într-un arbore în memorie (Memtable). Orice structuri de date de sprijin (filtre de înflorire și index rar) sunt, de asemenea, actualizate dacă este necesar.
• Când acest arbore devine prea mare, este scos pe disc cu cheile în ordine sortată.
• Când apare o citire, o verificăm folosind filtrul de înflorire. Dacă filtrul de înflorire indică faptul că valoarea nu este prezentă, atunci îi spunem clientului că cheia nu a putut fi găsită. Dacă filtrul de înflorire înseamnă că valoarea este prezentă, atunci începem să iterăm SSTables de la cel mai nou la cel mai vechi.
• complexitatea timpului LSM
  • Timp de citit: O(log(N)) unde N este numărul de înregistrări de pe disc
  • Ora scrierii: O(1) așa cum scrie în memorie
  • Ora ștergere: O(log(N)) unde N este numărul de înregistrări de pe disc
• Arborii LSM pot fi modificați la structuri de date mai eficiente folosind mai mult de 2 filtre. Unele dintre ele sunt bLSM, Diff-Index LSM.