LSM-træ (fra Log-structured merge-tree - log -structured merge tree) er en datastruktur, der bruges i mange DBMS'er , og som giver hurtig indeksadgang under forhold med hyppige indsættelsesanmodninger (for eksempel ved lagring af transaktionslogfiler ). LSM-træer gemmer ligesom andre træer nøgleværdi-par. Et LSM-træ opretholder to eller flere forskellige strukturer, der hver især er optimeret til den enhed, som det vil blive lagret på. Synkronisering mellem disse strukturer sker i blokke.
En simpel version af et LSM-træ, et to-niveau træ, består af to trælignende strukturer C 0 og C 1 . C 0 er mindre og lagres udelukkende i RAM, mens C 1 er i ikke-flygtig hukommelse. Nye poster indsættes i C 0 . Hvis størrelsen af C 0 efter indsættelse overstiger en forudbestemt tærskelværdi, fjernes det sammenhængende segment fra C 0 og slås sammen med C 1 ved vedvarende lagring. God ydeevne opnås på grund af det faktum, at træerne er optimeret til deres opbevaring, og sammenlægningen udføres effektivt og i grupper af flere poster ved hjælp af en algoritme, der minder om merge sort .
De fleste LSM-træer, der anvendes i praksis, implementerer flere niveauer. Niveau 0 (lad os kalde det MemTable) er gemt i RAM og kan repræsenteres af et almindeligt træ. Data på vedvarende lagringsenheder gemmes i form af tabeller sorteret efter nøgle ( SSTable ). Tabellen kan gemmes som en separat fil eller et sæt filer med ikke-overlappende nøgleværdier. For at finde en specifik nøgle, skal du tjekke for dens tilstedeværelse i MemTable og derefter gennemgå alle SSTables på den vedvarende lagerenhed.
Skema for at arbejde med LSM-træ:
Den søgte nøgle kan forekomme i flere tabeller på én gang på vedvarende lagerenheder, og det endelige svar afhænger af programmet. De fleste applikationer behøver kun den sidste værdi, der er knyttet til en given nøgle. Andre, såsom Apache Cassandra , hvor hver værdi er en databaserække (og en række kan have et forskelligt antal kolonner i forskellige tabeller fra vedvarende lagring), skal behandle alle værdierne på en eller anden måde for at få korrekt resultat [1] . For at reducere udførelsestiden for forespørgsler forsøger de i praksis at undgå situationen med for mange tabeller på vedvarende lagerenheder.
Der er udviklet udvidelser til "niveau"-metoden til at vedligeholde B+-strukturer , såsom bLSM [2] og Diff-Index. [3]
LSM-træarkitekturen giver dig mulighed for at opfylde en læseanmodning enten fra RAM eller i et opkald til vedvarende lagerenheder. At skrive er også altid hurtigt uanset lagerstørrelse.
SSTable på vedvarende lagerenheder er uforanderlig. Derfor gemmes ændringer i MemTable, og sletninger skal tilføje en særlig værdi til MemTable. Fordi nye læsninger sker sekventielt på tværs af indekset, vil den opdaterede værdi eller værdisletningsindtastning forekomme før de gamle værdier. En periodisk kørsel af sammenlægning af gamle SSTables på vedvarende lagring vil foretage disse ændringer og faktisk slette og opdatere værdier, hvilket slipper af med unødvendige data.
| Træ (datastruktur) | |
|---|---|
| Binære træer | |
| Selvbalancerende binære træer |
|
| B-træer | |
| præfiks træer |
|
| Binær opdeling af rummet | |
| Ikke-binære træer |
|
| At bryde rummet op |
|
| Andre træer |
|
| Algoritmer |
|