Log-Structured Merge-Tree
Subject: Computer and Technology noun /ˈlɔːɡˌstrʌktʃərd ˈmɜːrdʒˌtriː/ 1 definition
- data-structures
- storage-engines
- database-systems
- distributed-systems
-
Definition (noun)
Entry #232 · UpdatedA Log-Structured Merge-Tree (LSM) is a write-optimized storage data structure that converts random mutations into sequential disk I/O to sustain high write throughput. Incoming inserts, updates, and tombstone deletions are appended to a write-ahead log for durability and buffered in an ordered in-memory structure (memtable); when full, the memtable is flushed sequentially to disk as an immutable sorted run, typically an SSTable. Background compaction periodically merges and deduplicates overlapping runs across storage levels to reclaim space and keep lookups bounded. Unlike update-in-place B-trees, an LSM trades higher read complexity and compaction overhead—commonly mitigated with Bloom filters and sparse block indexes—for fast sequential ingestion and dense storage layout.
Common Types
Size-Tiered LSM: Accumulates multiple sorted runs of similar size within a tier and merges them once a count threshold is reached, minimizing write amplification at the cost of higher read and temporary space amplification.
Leveled LSM: Organizes levels below L0 into bounded, non-overlapping key-range files of exponentially growing capacity, keeping read and space amplification low while rewriting data more frequently during compaction (as in LevelDB and RocksDB).
Lazy-Leveled (Hybrid) LSM: Uses size-tiered merging in upper levels to absorb writes cheaply while maintaining a single leveled, non-overlapping run at the deepest level to bound worst-case space and point-lookup overhead.
Time-Windowed and FIFO LSM: Groups or expires immutable runs by age or storage budget—isolating merges to discrete time intervals or dropping the oldest runs without merging—to serve append-only telemetry and TTL-bound caches.
Example
An observability platform running RocksDB ingests 200,000 metric points per second into a memtable backed by a write-ahead log, flushing 64 MB immutable SSTables sequentially to NVMe storage as the buffer fills. Background compaction then merges overlapping L0 files into sorted L1 and L2 levels while purging overwritten versions and tombstones, keeping disk usage bounded and point queries fast via per-table Bloom filters.