LSM Tree (Log-Structured Merge Tree)

The Log-Structured Merge Tree, first described by Patrick O'Neil and colleagues in their 1996 paper, is a data structure designed to provide high write throughput on storage devices where sequential I/O is dramatically faster than random I/O. While B-trees modify data in place -- requiring random page writes for every update -- LSM trees convert all writes into sequential appends. This single design decision enables LSM trees to achieve 10-100x better write throughput than B-trees on traditional hard drives, and 3-10x better throughput on SSDs where the sequential-to-random performance gap is narrower.

The write path in an LSM tree is remarkably simple. When a write arrives, it is first appended to a write-ahead log (WAL) on disk for durability -- this is a sequential append and therefore fast. Simultaneously, the key-value pair is inserted into an in-memory sorted data structure called a memtable, typically implemented as a red-black tree, skip list, or adaptive radix tree. The memtable is sorted so it can later be written to disk as a sorted run. When the memtable reaches a configured size threshold (typically 64MB-256MB), it becomes immutable and a new empty memtable takes its place. The immutable memtable is then flushed to disk as a Sorted String Table (SSTable) -- a file where key-value pairs are written in sorted order. Because the memtable is already sorted, this flush is a single sequential write.

The read path is where LSM trees pay the cost of their write optimization. To find a key, the system must check the active memtable first, then the immutable memtable (if one exists), then each SSTable on disk from newest to oldest. In the worst case, every level must be checked. Bloom filters are the critical optimization that makes this practical: each SSTable includes a Bloom filter that can definitively say a key is NOT in that SSTable, allowing the reader to skip it entirely. With properly tuned Bloom filters (10 bits per key yields approximately 1% false positive rate), the system typically reads only 1-2 SSTables per point lookup instead of checking all of them.

Compaction is the background process that keeps the LSM tree healthy. Without compaction, SSTables accumulate endlessly, degrading read performance and wasting space (because superseded values in older SSTables are never reclaimed). Compaction merges multiple SSTables into fewer, larger SSTables, discarding deleted keys (tombstones) and superseded values in the process. The two dominant compaction strategies are size-tiered compaction (used by Cassandra by default), which groups SSTables of similar size and merges them when enough accumulate, and leveled compaction (used by RocksDB by default), which organizes SSTables into levels where each level is 10x larger than the previous and guarantees no overlapping key ranges within a level. Leveled compaction provides better read performance and more predictable space usage, but amplifies writes because data is rewritten with every level-to-level merge.

Imagine you are recording transactions throughout the day. Instead of finding the right page in a sorted ledger for each entry (like a B-tree), you write each transaction on a sticky note and add it to a sorted stack on your desk (the memtable). When the stack gets too tall, you file the entire sorted batch into a filing cabinet drawer as one sorted bundle (SSTable flush). Periodically, you consolidate multiple drawers by merging their sorted bundles into one larger sorted file and throwing away outdated entries (compaction). To look something up, you first check your current sticky note stack, then check each drawer from newest to oldest. To avoid opening every drawer, you tape a quick-reference list on each drawer saying which letters are NOT inside (the Bloom filter).