Stromy B+ a Stromy LSM sú dve základné dátové štruktúry, keď hovoríme o stavebných blokoch databázy. Stromy B+ sa používajú, keď potrebujeme menej času na vyhľadávanie a vkladanie, a na druhej strane stromy LSM sa používajú, keď máme súbory údajov náročné na zápis a čítanie nie je také vysoké.

Tento článok vás naučí Log Structured Merge Tree aka Strom LSM . Stromy LSM sú dátovou štruktúrou, ktorá je základom mnohých vysoko škálovateľných databáz typu kľúč-hodnota distribuovaných NoSQL, ako sú Amazon's DynamoDB, Cassandra a ScyllaDB.

Stromy LSM

Jednoduchá verzia LSM Trees obsahuje 2 úrovne stromovej štruktúry údajov:

• Zapamätateľné a nachádza sa úplne v pamäti (povedzme T0)
• SStables uložené na disku (povedzme T1)

Jednoduchý strom LSM

Nové záznamy sa vložia do zapamätateľného komponentu T0. Ak vloženie spôsobí, že komponent T0 prekročí určitý prah veľkosti, súvislý segment záznamov sa odstráni z T0 a zlúči sa do T1 na disku.

Pracovný postup LSM

LSM primárne používa 3 koncepty na optimalizáciu operácií čítania a zápisu:

• Tabuľka triedených reťazcov (SSTables) : Údaje sú zoradené v zoradenom poradí, takže pri každom čítaní údajov bude ich časová zložitosť v najhoršom prípade O( Log(N) ), kde N je počet záznamov v tabuľke databázy.

  1. SSTable

• Pamätný :
  • Štruktúra v pamäti
  • Ukladá údaje zoradené spôsobom
  • Funguje ako vyrovnávacia pamäť pre spätný zápis
  • Po dosiahnutí určitej veľkosti sa jeho údaje vyprázdnia ako SSTable do databázy
  • Ako sa zvyšuje počet SSTable na disku, a ak nejaký kľúč nie je prítomný v záznamoch
    • Pri čítaní tohto kľúča musíme prečítať všetky tabuľky SST, čo zvyšuje zložitosť času čítania.
    • Na prekonanie tohto problému prichádza do úvahy filter Bloom.
    • Bloom filter je priestorovo efektívna dátová štruktúra, ktorá nám môže povedať, či kľúč chýba v našich záznamoch s presnosťou 99,9 %.
    • Ak chcete použiť tento filter, môžeme doň pridať naše záznamy, keď sú zapísané, a skontrolovať kľúč na začiatku požiadaviek na čítanie, aby sme mohli požiadavky efektívnejšie obsluhovať, keď sa dostanú na prvé miesto.

Pamätná reprezentácia

• Zhutňovanie :
  • Keďže údaje ukladáme na disk ako SSTable, povedzme, že existujú N SSTable a veľkosť každej tabuľky je M
  • Potom najhorší prípad Čítať časová zložitosť je O( N* Log(M) )
  • Takže, ako počet SSTtables rastie Prečítajte si Časová zložitosť tiež zvyšuje.
  • Tiež, keď len vyprázdnime tabuľky SST v databáze, rovnaký kľúč je prítomný vo viacerých tabuľkách SST
  • Tu prichádza na rad použitie zhutňovača
  • Compactor beží na pozadí, spája SSTables a odstraňuje viacero riadkov s tým istým a pridáva nový kľúč s najnovšími dátami a ukladá ich do novej zlúčenej/komprimovanej SSTable.

3.1. SSTables sa vyprázdnili na disk

3.6. Kompaktor zhutnil 2 stoly SST na 1 stôl SST

Záver:

• Zápisy sú uložené v strome v pamäti (Memtable). V prípade potreby sa aktualizujú aj všetky podporné dátové štruktúry (filtre kvetov a riedky index).
• Keď sa tento strom stane príliš veľkým, vyprázdni sa na disk s kľúčmi v zoradenom poradí.
• Keď príde čítanie, skontrolujeme ho pomocou Bloomového filtra. Ak Bloom filter indikuje, že hodnota nie je prítomná, potom informujeme klienta, že kľúč sa nepodarilo nájsť. Ak Bloom filter znamená, že hodnota je prítomná, potom začneme iterovať SSTables od najnovších po najstaršie.
• Časová zložitosť LSM
  • Čas čítania: O(log(N)) kde N je počet záznamov na disku
  • Čas zápisu: O(1) ako sa píše v pamäti
  • Čas odstránenia: O(log(N)) kde N je počet záznamov na disku
• Stromy LSM môžu byť upravené na efektívnejšie dátové štruktúry pomocou viac ako 2 filtrov. Niektoré z nich sú bLSM, Diff-Index LSM.