Az LSM-fa (a Log-structured merge-tree - log- structed merge tree kifejezésből) számos DBMS -ben használt adatstruktúra , amely gyors indexelérést biztosít gyakori beszúrási kérések esetén (például tranzakciós naplók tárolásakor ). Az LSM fák más fákhoz hasonlóan kulcs-érték párokat tárolnak. Egy LSM-fa két vagy több különböző struktúrát tart fenn, amelyek mindegyike arra az eszközre van optimalizálva, amelyen tárolni fogja. A struktúrák közötti szinkronizálás blokkokban történik.
Az LSM fa egyszerű változata, egy kétszintű fa, két faszerű struktúrából áll, C 0 és C 1 . A C 0 kisebb, és teljes egészében a RAM-ban van tárolva, míg a C 1 a nem felejtő memóriában van. Az új bejegyzések a C 0 -ba kerülnek . Ha a beillesztés után a C 0 mérete meghalad egy előre meghatározott küszöbértéket, akkor az összefüggő szegmenst eltávolítják a C 0 -ból, és a folyamatos tárolás során egyesítik a C 1 -gyel. A jó teljesítményt az a tény éri el, hogy a fák tárolására optimalizálva vannak, és az összevonás hatékonyan, több rekordból álló csoportokban történik, egy összevonási rendezésre emlékeztető algoritmus segítségével .
A legtöbb gyakorlatban használt LSM fa több szintet valósít meg. A 0. szint (nevezzük MemTable-nek) a RAM-ban van tárolva, és egy normál fával ábrázolható. A perzisztens tárolóeszközök adatait kulcsok szerint rendezett táblázatok ( SSTable ) formájában tárolják. A táblázat tárolható külön fájlként vagy fájlok halmazaként, amelyek nem átfedő kulcsértékekkel rendelkeznek. Egy adott kulcs megtalálásához ellenőriznie kell annak jelenlétét a MemTable-ben, majd át kell tekintenie az állandó tárolóeszköz összes SST-tábláját.
Az LSM-fával való munka séma:
A keresett kulcs a perzisztens tárolóeszközökön egyszerre több táblázatban is megjelenhet, és a végső válasz a programtól függ. A legtöbb alkalmazásnak csak az adott kulcshoz tartozó utolsó értékre van szüksége. Másoknak, mint például az Apache Cassandra , amelyben minden érték egy adatbázissor (és egy sor különböző számú oszlopot tartalmazhat a perzisztens tárolástól eltérő táblázatokban), valamilyen módon fel kell dolgozni az összes értéket, hogy megkapja a helyes eredmény [1] . A lekérdezés végrehajtási idejének csökkentése érdekében a gyakorlatban igyekeznek elkerülni azt a helyzetet, hogy a perzisztens tárolóeszközökön túl sok tábla legyen.
A B+-struktúrák karbantartására szolgáló "szint" módszerhez kiterjesztéseket fejlesztettek ki , mint például a bLSM [2] és a Diff-Index. [3]
Az LSM-fa architektúra lehetővé teszi az olvasási kérések kielégítését akár RAM-ból, akár egyetlen hívással az állandó tárolóeszközök felé. Az írás is mindig gyors, függetlenül a tárhely méretétől.
Az állandó tárolóeszközökön lévő SSTable változatlan. Ezért a változtatásokat a MemTable tárolja, és a törléseknek speciális értéket kell hozzáadniuk a MemTable-hez. Mivel az új olvasások egymás után következnek be az indexben, a frissített érték vagy értéktörlési bejegyzés a régi értékek előtt fog megjelenni. A régi SST-táblák állandó tárolón rendszeresen futtatott egyesítése végrehajtja ezeket a változtatásokat, és ténylegesen törli és frissíti az értékeket, megszabadulva a szükségtelen adatoktól.
| Fa (adatstruktúra) | |
|---|---|
| Bináris fák | |
| Önkiegyensúlyozó bináris fák |
|
| B-fák | |
| előtag fák |
|
A tér bináris particionálása | |
| Nem bináris fák |
|
| A tér felosztása |
|
| Más fák |
|
| Algoritmusok |
|