Loggstrukturerat sammanslagningsträd
| Loggstrukturerat sammanslagningsträd | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Typ | Hybrid (två trädliknande komponenter) | ||||||||||||
| Uppfunnet | 1996 | ||||||||||||
| Uppfunnet av | Patrick O'Neil , Edward Cheng, Dieter Gawlick, Elizabeth O'Neil | ||||||||||||
| Tidskomplexitet i stor O-notation | |||||||||||||
| |||||||||||||
Inom datavetenskap är det loggstrukturerade sammanslagningsträdet (även känt som LSM-träd eller LSMT ) en datastruktur med prestandaegenskaper som gör den attraktiv för att tillhandahålla indexerad åtkomst till filer med hög insättningsvolym, såsom transaktionsloggdata . LSM-träd, precis som andra sökträd , upprätthåller nyckel-värdepar. LSM-träd upprätthåller data i två eller flera separata strukturer, som var och en är optimerad för sitt respektive underliggande lagringsmedium; data synkroniseras effektivt mellan de två strukturerna, i omgångar.
00000 En enkel version av LSM-trädet är ett LSM-träd med två nivåer. Såsom beskrivits av Patrick O'Neil , innefattar ett två-nivå LSM-träd två trädliknande strukturer, kallade C och C1 . C är mindre och helt inbyggt i minnet, medan C1 är inbyggt på disken. Nya poster infogas i den minnesresidenta C- komponenten. Om infogningen gör att C- komponenten överskrider en viss storlekströskel, tas ett sammanhängande segment av poster bort från C och slås samman till C 1 på disken. Prestandaegenskaperna hos LSM-träd härrör från det faktum att varje komponent är avstämd till egenskaperna hos dess underliggande lagringsmedium, och att data effektivt migreras över media i rullande batcher, med en algoritm som påminner om merge sort .
De flesta LSM-träd som används i praktiken har flera nivåer. Nivå 0 hålls i huvudminnet och kan representeras med hjälp av ett träd. Data på disken är organiserade i sorterade datakörningar . Varje körning innehåller data sorterad efter indexnyckeln. En körning kan representeras på disken som en enda fil, eller alternativt som en samling filer med icke-överlappande nyckelområden. För att utföra en fråga på en viss nyckel för att få dess tillhörande värde måste man söka i nivå 0-trädet och även varje körning. Stepped-Merge-versionen av LSM-trädet är en variant av LSM-trädet som stöder flera nivåer med flera trädstrukturer på varje nivå.
En speciell nyckel kan visas i flera körningar, och vad det betyder för en fråga beror på applikationen. Vissa applikationer vill helt enkelt ha det senaste nyckel-värdeparet med en given nyckel. Vissa applikationer måste kombinera värdena på något sätt för att få det korrekta sammanlagda värdet att returnera. Till exempel, i Apache Cassandra representerar varje värde en rad i en databas, och olika versioner av raden kan ha olika uppsättningar av kolumner.
För att hålla nere kostnaden för frågor måste systemet undvika en situation där det blir för många körningar.
Utvidgningar av den "utjämnade" metoden för att införliva B+-trädstrukturer har föreslagits, till exempel bLSM och Diff-Index. LSM-tree designades ursprungligen för skrivintensiva arbetsbelastningar. Eftersom allt fler läs- och skrivarbetsbelastningar samexisterar under en LSM-trädlagringsstruktur, kan läsdataåtkomster uppleva hög latens och låg genomströmning på grund av frekventa ogiltigförklaringar av cachad data i buffertcacher genom LSM-trädkomprimeringsoperationer. För att återaktivera effektiv buffertcache för snabb dataåtkomst föreslås och implementeras ett Log-Structured Buffered-Merged tree (LSbM-tree).
LSM-träd används i datalager som Apache AsterixDB , Bigtable , HBase , LevelDB , Apache Accumulo , SQLite4 , Tarantool , RocksDB , WiredTiger , Apache Cassandra , InfluxDB , YugabyteDB och ScyllaDB .
- Allmän
- O'Neil, Patrick E.; Cheng, Edward; Gawlick, Dieter; O'Neil, Elizabeth (juni 1996). "Det loggstrukturerade sammanslagningsträdet (LSM-träd)". Acta Informatica . 33 (4): 351–385. CiteSeerX 10.1.1.44.2782 . doi : 10.1007/s002360050048 .
- Li, Yinan; Han, Bingsheng; Luo, Qiong; Yi, Ke (2009). "Trädindexering på flashdiskar". 2009 IEEE 25:e internationella konferensen om datateknik . s. 1303–6. CiteSeerX 10.1.1.144.6961 . doi : 10.1109/ICDE.2009.226 . ISBN 978-1-4244-3422-0 .
- Luo, Chen; Carey, Michael J. (juli 2019). "LSM-baserade lagringstekniker: en undersökning". VLDB Journal . arXiv : 1812.07527 . doi : 10.1007/s00778-019-00555-y .