B+ Drevesa in LSM drevesa sta dve osnovni podatkovni strukturi, ko govorimo o gradnikih Baze podatkov. Drevesa B+ se uporabljajo, ko potrebujemo manj časa za iskanje in vstavljanje, po drugi strani pa se drevesa LSM uporabljajo, ko imamo nabore podatkov z intenzivnim pisanjem in branja niso tako visoka.

Ta članek bo učil o Log Structured Merge Tree aka Drevo LSM . Drevesa LSM so podatkovna struktura, na kateri temeljijo številne zelo razširljive baze podatkov tipa ključ-vrednost NoSQL, kot so Amazon DynamoDB, Cassandra in ScyllaDB.

LSM drevesa

Preprosta različica dreves LSM obsega 2 ravni drevesne strukture podatkov:

• Memtable in se v celoti nahaja v pomnilniku (recimo T0)
• SStables, shranjene na disku (recimo T1)

Preprosto drevo LSM

Novi zapisi se vstavijo v komponento memtable T0. Če vstavljanje povzroči, da komponenta T0 preseže določen prag velikosti, se sosednji segment vnosov odstrani iz T0 in združi v T1 na disku.

Potek dela LSM

LSM uporablja predvsem 3 koncepte za optimizacijo operacij branja in pisanja:

• Tabela razvrščenih nizov (SSTables) : Podatki so razvrščeni v razvrščenem vrstnem redu, tako da bo kadarkoli podatke preberete, njihova časovna zapletenost v najslabšem primeru O( Log(N) ), kjer je N število vnosov v tabeli zbirke podatkov.

  1. SSTable

• Memtable :
  • Struktura v pomnilniku
  • Shranjuje podatke na razvrščen način
  • Deluje kot predpomnilnik za povratno pisanje
  • Ko doseže določeno velikost, se njeni podatki splaknejo kot SSTable v zbirko podatkov
  • Ker se število SSTable poveča na disku in če kakšen ključ ni prisoten v zapisih
    • Med branjem tega ključa moramo prebrati vse SSTables, kar poveča kompleksnost časa branja.
    • Da bi rešili to težavo, se pojavi filter Bloom.
    • Bloomov filter je prostorsko učinkovita podatkovna struktura, ki nam lahko pove, če v naših zapisih manjka ključ s stopnjo natančnosti 99,9 %.
    • Za uporabo tega filtra lahko vanj dodamo svoje vnose, ko so napisani, in preverimo ključ na začetku zahtev za branje, da bi bolj učinkovito služili zahtevam, ko pridejo na prvo mesto.

Memtabilna predstavitev

• Zbijanje :
  • Ker podatke shranjujemo kot SSTable na disku, recimo, da obstajajo n SSTable in velikost vsake tabele je M
  • Potem v najslabšem primeru Preberi časovna kompleksnost je O( N* Log(M) )
  • Torej, ko se število tabel SST povečuje, Preberite časovno zapletenost se tudi poveča.
  • Poleg tega, ko samo izpiramo tabele SSTables v zbirki podatkov, je isti ključ prisoten v več tabelah SSTables
  • Tukaj pride do uporabe kompaktorja
  • Kompaktor deluje v ozadju, združuje SSTables in odstrani več vrstic z istimi ter doda nov ključ z najnovejšimi podatki in jih shrani v novo združeno/stisnjeno SSTable.

3.1. SSTables splaknjen na Disk

3.6. Kompaktor je stisnil 2 SSTtable v 1 SSTtable

Zaključek:

• Zapisi so shranjeni v drevesu v pomnilniku (Memtable). Po potrebi se posodobijo tudi vse podporne podatkovne strukture (filtri cvetenja in redki indeks).
• Ko to drevo postane preveliko, se splakne na disk s ključi v razvrščenem vrstnem redu.
• Ko pride branje, ga preverimo z uporabo bloom filtra. Če bloom filter kaže, da vrednost ni prisotna, odjemalcu povemo, da ključa ni bilo mogoče najti. Če bloom filter pomeni, da je vrednost prisotna, začnemo ponavljati SSTables od najnovejših do najstarejših.
• Časovna zapletenost LSM
  • Čas branja: O(log(N)) kjer je N število zapisov na disku
  • Čas pisanja: O(1) kot piše v pomnilniku
  • Izbriši čas: O(log(N)) kjer je N število zapisov na disku
• Drevesa LSM je mogoče spremeniti v učinkovitejše podatkovne strukture z uporabo več kot dveh filtrov. Nekateri od njih so bLSM, Diff-Index LSM.