Strom LSM (od Log-structured merge-tree - log -structured merge tree) je datová struktura používaná v mnoha DBMS , která poskytuje rychlý přístup k indexu v podmínkách častých požadavků na vkládání (například při ukládání transakčních protokolů ). Stromy LSM, stejně jako jiné stromy, ukládají páry klíč–hodnota. Strom LSM udržuje dvě nebo více různých struktur, z nichž každá je optimalizovaná pro zařízení, na kterém bude uložena. Synchronizace mezi těmito strukturami probíhá v blocích.
Jednoduchá verze LSM stromu, dvouúrovňový strom, se skládá ze dvou stromových struktur C 0 a C 1 . C 0 je menší a je celý uložen v paměti RAM, zatímco C 1 je v energeticky nezávislé paměti. Nové položky se vkládají do C 0 . Pokud po vložení velikost Co překročí určitou předem stanovenou prahovou hodnotu, souvislý segment je odstraněn z Co a sloučen s C1 při trvalém ukládání. Dobrého výkonu je dosaženo díky skutečnosti, že stromy jsou optimalizovány pro jejich ukládání a sloučení se provádí efektivně a ve skupinách několika záznamů pomocí algoritmu připomínajícího slučovací řazení .
Většina LSM stromů používaných v praxi implementuje několik úrovní. Úroveň 0 (říkejme jí MemTable) je uložena v paměti RAM a může být reprezentována běžným stromem. Data na perzistentních úložných zařízeních jsou ukládána ve formě tabulek seřazených podle klíče ( SSTable ). Tabulku lze uložit jako samostatný soubor nebo jako sadu souborů s nepřekrývajícími se hodnotami klíče. Chcete-li najít konkrétní klíč, musíte zkontrolovat jeho přítomnost v MemTable a poté projít všechny SSTables na trvalém úložném zařízení.
Schéma práce se stromem LSM:
Hledaný klíč se může objevit v několika tabulkách najednou na perzistentních úložných zařízeních a konečná odpověď závisí na programu. Většina aplikací potřebuje pouze poslední hodnotu spojenou s daným klíčem. Jiní, jako je Apache Cassandra , ve kterém je každá hodnota řádkem databáze (a řádek může mít různý počet sloupců v různých tabulkách z trvalého úložiště), musí všechny hodnoty nějakým způsobem zpracovat, aby získali správný výsledek [1] . Aby se zkrátila doba provádění dotazu, v praxi se snaží vyhnout situaci s příliš mnoha tabulkami na perzistentních úložných zařízeních.
Byla vyvinuta rozšíření „úrovňové“ metody pro udržování B+-struktur , jako je bLSM [2] a Diff-Index. [3]
Stromová architektura LSM vám umožňuje uspokojit požadavek na čtení buď z paměti RAM, nebo v jednom volání na zařízení s trvalým úložištěm. Zápis je také vždy rychlý bez ohledu na velikost úložiště.
SSTable na perzistentních úložných zařízeních je neměnný. Proto jsou změny uloženy v MemTable a odstranění musí přidat zvláštní hodnotu do MemTable. Protože k novým čtením dochází postupně v indexu, aktualizovaná hodnota nebo položka odstranění hodnoty se objeví před starými hodnotami. Pravidelně spouštěné slučování starých SSTables na trvalém úložišti provede tyto změny a skutečně odstraní a aktualizuje hodnoty, čímž se zbaví nepotřebných dat.
Strom (datová struktura) | |
---|---|
Binární stromy | |
Samovyrovnávací binární stromy |
|
B-stromy |
|
předponové stromy |
|
Binární dělení prostoru | |
Nebinární stromy |
|
Rozbití prostoru |
|
Jiné stromy |
|
Algoritmy |
|