LSM Tree

An LSM tree is a way to store sorted key-value data that is tuned for fast writes. Instead of editing data where it already sits on disk, which is what a B-tree does, an LSM tree only ever appends. New writes land in memory first, and disk files are written once and never modified again.

It has three moving parts. The memtable is a sorted in-memory structure, usually a skip list or red-black tree, that absorbs every incoming write. A Write-Ahead Log (WAL) records each write to disk first so nothing is lost on a crash. SSTables (Sorted String Tables) are immutable sorted files on disk that hold the flushed data.

Because every disk file is sorted and immutable, the engine never has to seek around to update a page. It writes one big sequential block at a time, which is the whole reason LSM trees exist.

Every write goes to the WAL and the memtable at the same time. The memtable keeps keys sorted as they arrive, so reads of recently written data are served straight from RAM. When the memtable fills up, typically at 64 to 256 MB, it is frozen and written to disk as a single new SSTable in one sequential pass.

Over time you accumulate many SSTables. Reads now have to check the memtable, then each SSTable from newest to oldest, because a newer file may hold an updated value or a tombstone marking a deletion. Two structures keep this cheap. A bloom filter per SSTable answers definitely not here without touching disk, and a sparse index per file points reads near the right offset.

Compaction is the background job that keeps things from sprawling. It merges several SSTables into fewer, larger sorted files, drops overwritten and deleted entries, and deletes the old files. Two common strategies are size-tiered, which merges files of similar size and is used by Cassandra by default, and leveled, which keeps non-overlapping key ranges per level and is the default in RocksDB and LevelDB.

Reach for an LSM-backed store when your workload is write-heavy: IoT sensor streams, application logs, event ingestion, time-series metrics, or any system where writes vastly outnumber reads. Sequential writes are roughly 100x faster than random writes on SSDs and around 1000x on spinning disks, so the gap over a B-tree is large under load.

The cost is read amplification and write amplification. A point lookup may consult several files, and a range scan has to merge data spread across levels, so reads are more work than the single-tree lookup a B-tree gives you. Compaction also rewrites data repeatedly: leveled compaction can physically write each value 10 to 30 times as it sinks through levels, which wears SSDs faster and competes for I/O.

If your workload is read-heavy with lots of complex range queries, a B-tree engine like PostgreSQL or InnoDB is simpler and more predictable. Most distributed databases pick LSM trees anyway, because replication and reconciliation make them write-heavy by nature, and the columnar data tends to compress well.

Picture a fleet of delivery trucks each pushing a GPS ping every few seconds into Cassandra. That is a flood of small writes with almost no in-place updates. Each ping appends to the WAL and the memtable, the memtable flushes to an SSTable when it fills, and compaction quietly stitches the files together overnight.

Reading the last hour for one truck is a short range scan that the bloom filters and per-level indexes make fast, while the heavy ingest never blocks because it never seeks to random disk pages. A B-tree handling the same firehose would thrash on random page updates and splits.

This is exactly why RocksDB sits underneath CockroachDB, TiKV, and Kafka Streams state stores, and why Cassandra and ScyllaDB chose the LSM design for their core engines.