# 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|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-vs-s3-files|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.