LSM Tree

A Log-Structured Merge tree is a write-optimized storage structure. Instead of updating data in place (like a B-tree), it buffers writes in memory, flushes them as immutable sorted files, and periodically merges those files in the background.

Core components

MemTable — an in-memory sorted structure (skip list or red-black tree) that accumulates writes. Sorted order means the flush to disk produces a sorted file without a separate sort step.

Write Ahead Log (WAL) — a sequential append-only log on disk. Every write hits the WAL before the MemTable. If the process crashes, the WAL replays to reconstruct the MemTable. The log-before-you-write rule and the recovery protocol built on it predate LSM trees by decades; Gray and Reuter's transaction-processing is the end-to-end treatment, down to what a checkpoint has to record for replay to be correct.

SSTable (Sorted String Table) — an immutable file of sorted key-value pairs written when the MemTable reaches its size threshold. Once on disk, an SSTable is never modified.

Bloom filter — a probabilistic membership test per SSTable, kept in RAM. Answers "definitely not here" or "maybe here," avoiding most unnecessary disk reads.

Write path

1. Append to WAL (sequential disk write)
2. Insert into MemTable (RAM)
3. When MemTable is full, freeze it and flush to a new SSTable
4. Clear the WAL segment for the flushed MemTable

All disk writes are sequential — no random I/O. This is why LSM trees handle write-heavy workloads better than B-trees, where every update is a random page write.

Read path

1. Check the MemTable
2. Check SSTables newest-to-oldest, stopping at the first match
3. Bloom filter gates each SSTable check — skip the file if the filter says "not here"

Reads are slower than B-trees in the worst case because they may touch multiple files. The tradeoff is explicit: optimize writes at the cost of read amplification, then mitigate read cost with Bloom filters and compaction.

Compaction

Background merge of SSTables to reduce file count, reclaim space from stale versions, and remove tombstones (deletion markers). Two strategies:

• Leveled (RocksDB, LevelDB) — aggressive merging into fixed-size levels. Fewer files per level means faster reads, but more write amplification from frequent compaction.
• Size-tiered (Cassandra) — merge files of similar size. Less write amplification, but read latency varies as file counts fluctuate.

Where it's used

Cassandra, RocksDB, LevelDB, HBase, ScyllaDB, CockroachDB (via RocksDB/Pebble), and many embedded storage engines. RocksDB in particular has become a building block — it's the storage layer under TiKV, MyRocks (MySQL), and MongoRocks. ingodb takes the LSM foundation further with reactive indexing — the engine watches query patterns and creates secondary SSTables sorted by frequently-filtered fields.

Relationship to other concepts

LSM trees and B-trees represent the two poles of database storage design: append-only vs in-place mutation, write-optimized vs read-optimized. Most real systems blend strategies — for example, using an LSM tree for the write path but caching hot data in memory for reads, or using B-trees with write-ahead logging to get some of each. Kleppmann's designing-data-intensive-applications works that comparison out properly — the storage-engine chapter is the standard place people are sent to understand why a system picked one pole over the other.

The inverted-index used in full-text search is a separate structure, but systems like Elasticsearch layer inverted indexes on top of LSM-based segment storage (Lucene segments are conceptually similar to SSTables — immutable, periodically merged).

ZeroFS is a filesystem application of the same pattern: it keeps its metadata in an LSM tree while packing file extents into immutable, encrypted object-storage segments.