The problem: two workloads, two engines
Snip runs two very different stores:
- Links in Postgres: 600 million rows, read 100,000 times a second (mostly via cache), occasionally edited.
- Click history in a Cassandra-style cluster: billions of tiny rows, written tens of thousands of times a second, never edited, read in bulk for analytics.
Postgres uses B-trees. Cassandra, RocksDB, ScyllaDB and many others use LSM-trees. Both keep keys sorted, which fixes the hash index's problems from 09.01 A storage engine is a log and an index. They differ in when the sorting work happens.
B-trees: sorted pages, updated in place
A B-tree stores keys in sorted, fixed-size pages on disk: usually 8 kB in Postgres, 16 KB by default in MySQL's InnoDB. Each page holds hundreds of keys and pointers, so a few levels cover billions of rows, and a lookup reads three or four pages (04.02 Indexes and B-trees).
To change a value, the engine finds its page and rewrites the page in place. For crash safety, the change first goes to the write-ahead log (04.06 Write-ahead logs and crash recovery). So one small update costs a log record and eventually an 8 kB page write, even if one byte changed. If the page is full, it splits in two, updating the parent too.
LSM-trees: write sorted files once, merge later
A log-structured merge-tree never updates in place. Writes go to a sorted structure in memory (the memtable), plus a write-ahead log for safety. When the memtable fills, it's written out in one sequential pass as an immutable sorted file. Files pile up, so a background process compacts them: merging several sorted files into one, keeping only the newest version of each key and dropping deleted ones. A read checks the memtable, then files from newest to oldest, skipping most of them with a Bloom filter per file. 09.03 The LSM write and read path walks through it with a lab.
Three kinds of amplification
Storage engines are compared by how much extra work they do beyond what you asked:
- Write amplification: bytes written to disk per byte you wrote. B-trees rewrite whole pages; LSM-trees rewrite data each time compaction merges it.
- Read amplification: pages or files touched per lookup. B-trees: one path down the tree. LSM-trees: possibly several files.
- Space amplification: disk used per byte of live data. B-trees leave pages partly empty; LSM-trees keep old versions until compaction removes them.
Mark Callaghan's blog on database performance puts the rule bluntly: an algorithm can optimise for at most two of read, write and space amplification.
| B-tree | LSM-tree | |
|---|---|---|
| Writes | Random page rewrites; higher write amplification for small updates | Sequential writes; batched; usually higher throughput |
| Point reads | Predictable: one path down the tree | Memtable plus some files; Bloom filters keep it close |
| Range scans | Excellent: keys are in sorted pages | Good, but must merge across files |
| Space | Pages partly empty after splits | Dead versions until compacted; compact well and it's tight |
| Background work | Vacuum (in Postgres) and page splits | Compaction, which competes with foreground traffic |
| Latency | Steady | Occasional spikes when compaction falls behind |
| Typical | Postgres, MySQL InnoDB, SQLite | RocksDB, Cassandra, ScyllaDB, LevelDB |
So the click history goes to an LSM store: it's write-heavy, never updated in place, and read mostly in big scans. Links stay in a B-tree: updates are rare, reads must be fast and predictable, and Postgres's transactions and indexes are worth having.
Seen in production
Mark Callaghan
2015Read, write and space amplification
Callaghan argues that an algorithm can optimise for at most two of read, write and space amplification. As one example, a B-tree has less read amplification than an LSM-tree, while an LSM-tree has less write amplification than a B-tree.
What we foundNo storage engine minimises all three amplifications; B-trees favour reads, LSM-trees favour writes.
Read, write & space amplification: pick 2 (Small Datum)smalldatum.blogspot.com ↗Meta
WikiRocksDB
New writes go into an in-memory memtable and, optionally, a write-ahead log. When the memtable fills, it's flushed to a sorted file on storage. RocksDB's primary design point is performance on fast storage for server workloads, and its architecture is meant to make it easy to tune trade-offs for different workloads: its default leveled compaction optimises space amplification, while universal compaction typically gives lower write amplification but higher space and read amplification.
What we foundAn LSM engine built for fast storage, with the amplification trade-offs exposed as settings.
RocksDB Overview (RocksDB wiki)github.com ↗A metrics service ingests 500,000 small data points a second, never updates them, and reads them as time ranges for dashboards. Which engine family fits, and what's the main cost to watch?
Recap
Interview questions
Compare B-trees and LSM-trees. When would you choose each?