B+ stromy a Stromy LSM jsou dvě základní datové struktury, když mluvíme o stavebních kamenech Databáze. Stromy B+ se používají, když potřebujeme méně času na vyhledávání a vkládání, a na druhou stranu stromy LSM se používají, když máme datové sady náročné na zápis a čtení není tak vysoké.

Tento článek bude učit o Log strukturovaný slučovací strom aka Strom LSM . Stromy LSM jsou datovou strukturou, která je základem mnoha vysoce škálovatelných databází typu klíč-hodnota distribuovaných NoSQL, jako jsou Amazon's DynamoDB, Cassandra a ScyllaDB.

Stromy LSM

Jednoduchá verze LSM Trees obsahuje 2 úrovně stromové struktury dat:

• Zapamatovatelný a je zcela uložen v paměti (řekněme T0)
• SStables uložené na disku (řekněme T1)

Jednoduchý strom LSM

Nové záznamy jsou vloženy do memtable komponenty T0. Pokud vložení způsobí, že komponenta T0 překročí určitou prahovou hodnotu velikosti, souvislý segment položek je z T0 odstraněn a sloučen do T1 na disku.

Pracovní postup LSM

LSM primárně používá 3 koncepty pro optimalizaci operací čtení a zápisu:

• Tabulka seřazených řetězců (SSTables) : Data jsou řazena v seřazeném pořadí, takže při každém čtení dat bude jejich časová složitost v nejhorším případě O( Log(N) ), kde N je počet záznamů v tabulce databáze.

  1. SSTable

• Zapamatovatelný :
  • Struktura v paměti
  • Ukládá data seřazeným způsobem
  • Funguje jako mezipaměť pro zpětný zápis
  • Po dosažení určité velikosti jsou jeho data vyprázdněna jako SSTable do databáze
  • Počet SSTable se zvýší na disku a pokud v záznamech není přítomen nějaký klíč
    • Při čtení tohoto klíče musíme číst všechny tabulky SST, což zvyšuje složitost doby čtení.
    • K překonání tohoto problému přichází na scénu filtr Bloom.
    • Bloomův filtr je prostorově efektivní datová struktura, která nám může s přesností 99,9 % sdělit, zda klíč chybí v našich záznamech.
    • Chcete-li použít tento filtr, můžeme do něj přidat naše záznamy, když jsou zapsány, a zkontrolovat klíč na začátku požadavků na čtení, abychom požadavky obsluhovali efektivněji, když přijdou na prvním místě.

Zapamatovatelná reprezentace

• Zhutňování :
  • Protože data ukládáme na disk jako SSTable, řekněme, že existují N SSTable a velikost každé tabulky je M
  • Pak nejhorší případ Číst časová složitost je O( N* Log(M) )
  • Takže, jak se počet SSTables zvyšuje Přečtěte si Časová složitost také zvyšuje.
  • Také, když právě vyprázdníme SSTables v databázi, stejný klíč je přítomen ve více SSTables
  • Zde přichází na řadu použití kompaktoru
  • Compactor běží na pozadí, sloučí SSTables a odstraní několik řádků se stejným a přidá nový klíč s nejnovějšími daty a uloží je do nového sloučeného/zkomprimovaného SSTable.

3.1. SSTables vyprázdněny na disk

3.6. Kompaktor zhutnil 2 SSTtables na 1 SSTtable

Závěr:

• Zápisy jsou uloženy ve stromu v paměti (Memtable). V případě potřeby jsou také aktualizovány všechny podpůrné datové struktury (filtry květů a řídký index).
• Když se tento strom stane příliš velkým, je vyprázdněn na disk s klíči v seřazeném pořadí.
• Když přijde čtení, zkontrolujeme to pomocí Bloomova filtru. Pokud Bloomův filtr indikuje, že hodnota není přítomna, pak klientovi sdělíme, že klíč nebyl nalezen. Pokud Bloomův filtr znamená, že hodnota je přítomna, pak začneme iterovat SSTables od nejnovější k nejstarší.
• Časová složitost LSM
  • Čas čtení: O(log(N)) kde N je počet záznamů na disku
  • Čas zápisu: O(1) jak se píše v paměti
  • Čas smazání: O(log(N)) kde N je počet záznamů na disku
• Stromy LSM lze upravit na efektivnější datové struktury pomocí více než 2 filtrů. Některé z nich jsou bLSM, Diff-Index LSM.