LSM tree
A Log-Structured Merge-tree (LSM tree) is a storage structure designed to make writes as fast as possible by turning random writes into sequential ones [1]. Traditional disk-based structures like the B-tree update data in place, which means a write can trigger a random seek to wherever the existing record lives on disk. LSM trees avoid this completely: every write goes into memory first, and data only reaches disk in large, sorted, sequential batches. This makes LSM trees the default choice for write-heavy workloads.
Think of it like a notebook system. You jot new entries into a small notepad in your pocket (memory). When the notepad is full, you copy everything neatly into a bigger sorted binder (disk). Occasionally you merge older binders together to keep things tidy. You never erase and rewrite in the middle of a page.
How writes work
Every incoming write goes to two places at once:
- A Write-Ahead Log (WAL): a simple append-only file on disk, used only for crash recovery. If the machine dies, the WAL lets the database replay lost writes.
- A MemTable: an in-memory sorted structure (often a skip list or a balanced tree). This is where active writes live.
When the MemTable fills up, it is flushed to disk as an SSTable (Sorted String Table): an immutable, sorted file. The flush is one big sequential write, which is the fastest kind of disk operation.
Over time, many SSTables pile up across multiple levels (L0, L1, L2...). Each level is larger than the last, and a background process called Compaction periodically merges SSTables together, removes deleted keys, and keeps each level sorted and compact.
How reads work
Reads are more expensive in an LSM tree because data could be in memory or in any level on disk. The lookup order is:
- Check the MemTable first (most recent data)
- Check L0 SSTables (next most recent)
- Go deeper through levels until the key is found
To avoid checking every SSTable, databases use a Bloom filter per SSTable: a small probabilistic structure that can quickly say "this key is definitely not in this file", skipping unnecessary reads. This brings read performance close to acceptable for most workloads.
LSM tree vs B-tree
| Feature | LSM tree | B-tree |
|---|---|---|
| Write speed | Very fast (sequential) | Slower (random, in-place) |
| Read speed | Slower (multi-level lookup) | Faster (direct path) |
| Space usage | Higher (until compaction) | Lower (in-place updates) |
| Best for | Write-heavy workloads | Read-heavy or mixed workloads |
| Compaction cost | Background CPU/IO needed | No compaction needed |
Where LSM trees are used
LSM trees power most major NoSQL databases built for high write throughput:
- Cassandra and ScyllaDB: distributed wide-column stores
- RocksDB: a key-value engine used by many other databases (including CockroachDB and TiKV)
- LevelDB: Google's original LSM-based key-value store
- Apache HBase: Hadoop's distributed database
- InfluxDB: time-series data