LSM-Trees

The B-tree is the workhorse behind most traditional databases (PostgreSQL, MySQL, SQLite). It is a balanced tree stored on disk that supports fast reads by keeping data sorted and directly locatable in O(log n) page lookups.

But writes in a B-tree have a painful property: they update the tree in place. Inserting a single row might require reading a leaf page into memory, modifying it, and writing it back to its original location on disk. That is a random write, and random writes are the slow path for both spinning disks and SSDs:

• On spinning disks, the read/write head must physically seek to the correct track. Seek time (5-10ms) dominates latency. A database doing thousands of random writes per second spends most of its time waiting for the disk head.
• On SSDs, there is no seek penalty, but random writes still cause write amplification: SSDs must erase an entire block (often 512KB) before rewriting even a single byte. Frequent small random writes wear out flash cells faster and reduce throughput.

For write-heavy workloads (logging, time-series, event streams), this is a serious bottleneck.

Log-Structured Merge-Trees (LSM-Trees) flip the write model. Instead of touching files on disk immediately, they:

1. Buffer writes in memory (fast).
2. When the buffer is full, flush it to disk in one sequential write (fast, because the disk head does not need to seek anywhere).
3. Later, merge and sort files in the background (sequential reads and writes, the disk's happy path).

Think of it like a busy restaurant kitchen. Instead of a waiter running to the storage room for every single ingredient request (random access), the kitchen manager batches all the day's orders, prepares a consolidated list, and restocks everything in a single organized trip (sequential access). The cost per item drops dramatically.

Stage 1: Memtable

Every write (insert or update) goes first to the Memtable, an in-memory sorted data structure, typically implemented as a red-black tree or skip list. Because it is in memory, writes are extremely fast. The Memtable keeps keys sorted at all times so a flush produces a sorted file without extra work.

Stage 2: Write-Ahead Log (WAL)

Before acknowledging a write, the database also appends it to the Write-Ahead Log, a simple append-only file on disk. The WAL is not sorted and is not meant for reads. Its sole purpose is crash recovery: if the process crashes before the Memtable is flushed, the WAL lets the database replay the lost writes on restart.

The WAL write is sequential (always append), so it is fast even on spinning disk.

Stage 3: SSTables

When the Memtable reaches a size threshold (e.g., 64 MB), it is flushed to disk as a new SSTable (Sorted String Table). An SSTable is:

• Immutable: once written, it is never modified.
• Sorted: all keys are stored in order, enabling binary search and efficient merging.
• Self-indexed: an index block at the end of the file maps key ranges to byte offsets inside the file.

Newly flushed SSTables land at Level 0. Over time, a background compaction process merges smaller SSTables into larger ones and promotes them to deeper levels (Level 1, Level 2, ...).

The write path is fast, but reads pay a cost called read amplification.

To find a key, the database must check:

1. The Memtable (in memory, fast).
2. Level 0 SSTables, from newest to oldest. Level 0 files can have overlapping key ranges, so multiple files may need to be checked.
3. Level 1, 2, 3... SSTables. Each level's files are non-overlapping, so at most one file per level needs checking.

In the worst case (a key that does not exist anywhere), you read one file at every level before concluding the key is missing. This is where Bloom filters make LSM-Trees practical.

Every SSTable carries a small Bloom filter in its index block. Before opening any SSTable file to look up a key, the database checks the filter:

• If the filter says "definitely absent," skip the file entirely. Zero I/O.
• If the filter says "possibly present," open the file and do a binary search.

With Bloom filters tuned to a ~1% false-positive rate, the database opens the wrong file only 1% of the time. Read amplification drops dramatically in practice.

Left unchecked, Level 0 would accumulate SSTables indefinitely. Reads would get slower as more files pile up. Compaction is the background process that prevents this.

Compaction takes a set of SSTables, merge-sorts them into a new, larger SSTable, and deletes the originals. Because all SSTables are already sorted, the merge is a simple k-way merge (the same algorithm used in merge sort), which is sequential I/O from start to finish.

Leveled compaction

Each level has a size budget. When a level exceeds its budget, one or more SSTables are picked and merged with the overlapping SSTables in the next level. Each level is typically 10x larger than the previous. This keeps reads predictable: at most one SSTable per level (except Level 0) can contain any given key range.

RocksDB, Cassandra (with LCS), and LevelDB all support leveled compaction.

Size-tiered compaction

Instead of fixed levels, SSTables of similar size are grouped and merged together. Writes are cheaper (fewer compaction bytes written), but reads are worse because more files can contain overlapping key ranges. Cassandra's default (STCS) uses this approach for write-dominated tables.

LSM-Trees cannot delete data immediately. Deleting from an immutable SSTable would require rewriting the entire file.

Instead, a delete writes a special marker called a tombstone into the Memtable alongside regular writes. The tombstone propagates through the system like any write, appearing in SSTables at each level. During compaction, when a tombstone is merged with the actual key-value entry, both are discarded. The data is physically removed only at that point.

This has an important consequence: deleted data continues to consume space until compaction reaches the level where both the tombstone and the original entry exist. For workloads with heavy deletes, it is important to tune compaction aggressively.

Neither is universally better. PostgreSQL and MySQL choose B-trees because their workloads are read-heavy and random. Kafka's internal log storage, time-series databases, and wide-column stores choose LSM-trees because they ingest data faster than they read it.

• RocksDB: a high-performance embedded key-value store from Meta, used as the storage engine for Kafka (KIP-630/KRaft), TiKV, CockroachDB, and MyRocks (MySQL variant).
• Apache Cassandra: a wide-column distributed database used at Apple, Netflix, and Discord. Each node uses an LSM-tree storage engine called the Cassandra Storage Engine.
• LevelDB: the open-source library from Google that pioneered the leveled compaction strategy. Used inside Chrome's IndexedDB.
• ScyllaDB: a C++ reimplementation of Cassandra with lower latency, using the same LSM-tree storage model.
• InfluxDB and TimescaleDB variants: time-series databases benefit from LSM because incoming data is naturally time-ordered and append-heavy.

• The Log-Structured Merge-Tree (LSM-Tree) original paper — O'Neil et al., 1996
• RocksDB: A Persistent Key-Value Store for Fast Storage — Meta Engineering
• Designing Data-Intensive Applications, Chapter 3 — Martin Kleppmann
• Cassandra Storage Engine: SSTables and Compaction
• LevelDB Implementation Notes — Google