Log-Structured Merge-Tree
E717514
A Log-Structured Merge-Tree (LSM-tree) is a write-optimized data structure that organizes data in sequential logs and periodically merges them to provide efficient writes and good read performance for key-value storage systems.
Statements (71)
| Predicate | Object |
|---|---|
| instanceOf |
data structure
ⓘ
index structure ⓘ write-optimized data structure ⓘ |
| advantageOverBTree | better performance on write-heavy workloads ⓘ |
| contrastedWith |
B+ tree
ⓘ
B-tree NERFINISHED ⓘ |
| describedIn | The Log-Structured Merge-Tree (LSM-Tree) paper NERFINISHED ⓘ |
| disadvantageComparedToBTree |
higher read amplification
ⓘ
higher space amplification ⓘ |
| hasAcronym | LSM-tree NERFINISHED ⓘ |
| hasComponent |
SSTable
NERFINISHED
ⓘ
compaction process ⓘ immutable memtable ⓘ memtable ⓘ multiple levels ⓘ sorted run ⓘ write-ahead log ⓘ |
| hasConcept |
hybrid compaction
ⓘ
leveling compaction ⓘ tiering compaction ⓘ |
| hasGoal |
efficient storage utilization
ⓘ
efficient writes ⓘ good read performance ⓘ |
| hasOperation |
compaction between levels
ⓘ
flush from memory to disk ⓘ merge of sorted runs ⓘ |
| hasProperty |
append-friendly
ⓘ
log-structured ⓘ merge-based ⓘ multi-level ⓘ sequential-write-oriented ⓘ supports compaction ⓘ supports high write throughput ⓘ supports point lookups ⓘ supports range queries ⓘ write-optimized ⓘ |
| introducedBy |
Dieter Gawlick
NERFINISHED
ⓘ
Edward Cheng NERFINISHED ⓘ Elizabeth O’Neil NERFINISHED ⓘ Patrick O’Neil NERFINISHED ⓘ |
| introducedIn | 1996 ⓘ |
| mitigatedBy |
Bloom filters
NERFINISHED
ⓘ
caching ⓘ careful compaction policies ⓘ |
| optimizesFor |
high write throughput
ⓘ
sequential disk writes ⓘ |
| organizesDataAs |
sequential logs
ⓘ
sorted runs on disk ⓘ |
| performs |
background compaction
ⓘ
periodic merges ⓘ |
| stores | key-value pairs ⓘ |
| supports |
deletions via tombstones
ⓘ
ordered iteration ⓘ range scans ⓘ upserts ⓘ |
| tradesOff |
read amplification
ⓘ
space amplification ⓘ write amplification ⓘ |
| usedFor |
NoSQL databases
ⓘ
key-value storage systems ⓘ log-structured file systems ⓘ log-structured storage ⓘ persistent key-value stores ⓘ write-intensive workloads ⓘ |
| usedIn |
Cassandra
NERFINISHED
ⓘ
HBase NERFINISHED ⓘ LevelDB NERFINISHED ⓘ RocksDB NERFINISHED ⓘ ScyllaDB NERFINISHED ⓘ WiredTiger storage engine NERFINISHED ⓘ many modern NoSQL systems ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.