Sloučený strom strukturovaný pomocí protokolu - Log-structured merge-tree

Sloučený strom strukturovaný pomocí protokolu
TypHybridní (dvě stromové komponenty)
Vynalezeno1996
VynalezlPatrick O'Neil Edward Cheng, Dieter Gawlick, Elizabeth O'Neil
Časová složitost v velká O notace
AlgoritmusPrůměrnýNejhorší případ
VložitO (1)O (1)
Najít-minNA)NA)
Odstranit-minNA)NA)

v počítačová věda, sloučený strom strukturovaný protokolem (nebo LSM strom) je a datová struktura s výkonovými charakteristikami, díky nimž je atraktivní pro poskytování indexováno přístup k souborům s velkým objemem vložení, jako je data transakčního protokolu. Stromy LSM, jako jiné hledat stromy, udržovat páry klíč – hodnota. Stromy LSM udržují data ve dvou nebo více samostatných strukturách, z nichž každá je optimalizována pro příslušné podkladové úložné médium; data jsou synchronizována mezi dvěma strukturami efektivně, v dávkách.

Jedna jednoduchá verze stromu LSM je dvouúrovňový strom LSM.[1]Jak popisuje Patrick O'Neil, dvouúrovňový strom LSM obsahuje dva jako strom struktury zvané C0 a C.1. C0 je menší a zcela rezidentní v paměti, zatímco C1 je rezidentem na disku. Nové záznamy jsou vloženy do paměti C rezidentní0 součástka. Pokud vložení způsobí C0 komponenta k překročení určité prahové hodnoty velikosti, je souvislý segment položek odstraněn z C0 a sloučeny do C.1 na disku. Výkonnostní charakteristiky stromů LSM vycházejí ze skutečnosti, že každá komponenta je vyladěna na charakteristiky jejího podkladového úložného média a že data jsou efektivně migrována napříč médii v postupných dávkách pomocí algoritmu připomínajícího Sloučit třídění.

Diagram ilustrující zhutnění dat ve sloučeném stromu strukturovaném podle protokolu
Diagram ilustrující zhutnění dat ve sloučeném stromu strukturovaném podle protokolu

Většina LSM stromů používaných v praxi využívá více úrovní. Úroveň 0 je uložena v hlavní paměti a může být reprezentována pomocí stromu. Data na disku jsou organizována do tříděných běhů dat. Každý běh obsahuje data seřazená podle indexového klíče. Běh může být na disku zastoupen jako jeden soubor nebo alternativně jako kolekce souborů s nepřekrývajícími se rozsahy kláves. Chcete-li provést dotaz na konkrétním klíči a získat jeho přidruženou hodnotu, musíte hledat ve stromu úrovně 0 a při každém spuštění.

Konkrétní klíč se může objevit v několika bězích a to, co to znamená pro dotaz, závisí na aplikaci. Některé aplikace jednoduše chtějí nejnovější pár klíč – hodnota s daným klíčem. Některé aplikace musí nějakým způsobem kombinovat hodnoty, aby se vrátila správná agregovaná hodnota. Například v Apache Cassandra, každá hodnota představuje řádek v databázi a různé verze řádku mohou mít různé sady sloupců.[2]

Aby se snížily náklady na dotazy, musí se systém vyhnout situaci, kdy je příliš mnoho běhů.

Rozšíření metody „vyrovnání“ B + strom byly navrženy struktury, například bLSM[3] a rozdílový index.[4]

Stromy LSM se používají v datových úložištích, jako jsou Bigtable, HBase, LevelDB, SQLite4[5], Tarantool [6],RocksDB, WiredTiger[7], Apache Cassandra, InfluxDB[8] a ScyllaDB.

Reference

  1. ^ O'Neil 1996, s. 4
  2. ^ "Vyrovnané zhutnění v Apache Cassandra: DataStax". 13. února 2014. Archivovány od originál 13. února 2014.
  3. ^ http://www.eecs.harvard.edu/~margo/cs165/papers/gp-lsm.pdf
  4. ^ http://researcher.ibm.com/researcher/files/us-wtan/DiffIndex-EDBT14-CR.pdf
  5. ^ „SQLite4 with LSM Wiki“. SQLite.
  6. ^ "Aplikační server společně se správcem databáze". Citováno 3. dubna 2018. Diskový úložný modul Tarantool je fúzí nápadů z moderních souborových systémů, logovaných strukturních sloučených stromů a klasických B-stromů.
  7. ^ „GitHub - wiredtiger / wiredtiger: zdrojový strom WiredTiger“. 4. prosince 2019 - prostřednictvím GitHub.
  8. ^ Dix, Paul (7. října 2015). „[Nový] Úložný modul InfluxDB | Časově strukturovaný sloučený strom“.
Všeobecné

externí odkazy