LSM Tree
A Log-Structured Merge-tree (LSM tree) is a write-optimized data structure that batches writes in memory and flushes them sequentially to disk as immutable sorted files, periodically merging (compacting) those files to control read cost…
Definition
A Log-Structured Merge-tree (LSM tree) is a write-optimized data structure that batches writes in memory and flushes them sequentially to disk as immutable sorted files, periodically merging (compacting) those files to control read cost and reclaim space.
Overview
The LSM tree was introduced by Patrick O'Neil and colleagues in a 1996 paper as an alternative to B-trees for workloads dominated by writes. Rather than updating data in place, an LSM tree accepts writes into an in-memory structure called a memtable (typically a skip list or balanced tree), also appending each write to an on-disk write-ahead log for durability. When the memtable reaches a size threshold, it is flushed to disk as an immutable, sorted file often called an SSTable (Sorted String Table). Over time many SSTables accumulate, and a background compaction process merges them, discarding overwritten or deleted keys (tombstones) and keeping the number of files a read must consult bounded. This design trades read amplification and space amplification for dramatically better write throughput, because writes are always sequential appends rather than random-access updates. Reads, however, may need to check the memtable and several SSTables before finding the most recent value for a key, which is why LSM-based systems commonly use Bloom filters to quickly skip SSTables that cannot contain a given key, and maintain sparse indexes into each SSTable to avoid scanning it fully. Compaction strategy — size-tiered versus leveled being the two dominant families — is the central tuning knob: size-tiered compaction favors write throughput at the cost of higher space and read amplification, while leveled compaction bounds space and read costs more tightly at the cost of more compaction I/O. LSM trees underpin most modern write-heavy storage engines: Google's Bigtable and LevelDB, Facebook's RocksDB, Apache Cassandra, HBase, ScyllaDB, and the storage layers of many time-series and log-oriented databases all use LSM trees rather than B-trees. They are especially well suited to workloads with high write volume, sequential or append-mostly ingestion, and where write latency matters more than worst-case read latency, which is why they are the default choice for logging, metrics, event-sourcing, and many NoSQL systems.
Key Concepts
- Writes are buffered in an in-memory memtable before being flushed to disk
- On-disk data is stored as immutable, sorted SSTable files
- Background compaction merges SSTables and removes obsolete/deleted entries
- Bloom filters accelerate reads by skipping SSTables that cannot contain a key
- Write-ahead logging provides durability for data still in the memtable
- Sequential disk writes replace random-access updates, boosting write throughput
- Tunable compaction strategy (size-tiered vs. leveled) trades off write, read, and space amplification
- Naturally supports range scans due to sorted SSTable layout