LSM trees and B-trees
The two ways disks store sorted data, and why writes and reads favour different ones.
01The intuition
The problem it solves
Two shopkeepers keep accounts. The first keeps a ledger with a page per customer, sorted by name; every sale means finding the page and writing on it, and finding any customer's balance is quick. The second scribbles every sale into a notebook in the order it happens, fast as can be, and once a week sorts the week's pages into neat sorted bundles; finding a balance means checking the latest bundle, then older ones. The first is slow to write and fast to read; the second is fast to write and a little slower to read.
These are the two ways a database keeps sorted data on disk. The B-tree is the ledger. The LSM tree (log-structured merge tree) is the notebook with periodic sorting. Which one a store uses decides whether it is good at absorbing writes or at answering reads, and an interviewer asking "why that database?" is often asking which of these you want.
Build it one piece at a time
Step 1: the B-tree. Data lives in fixed-size pages (say 8 KB) arranged as a wide, shallow tree sorted by key. A lookup walks from the root down three or four levels and reads one leaf page. A write finds the leaf and changes it in place; if the leaf is full it splits. Every write is a random disk write.
Step 2: the LSM write path. A write goes to an in-memory sorted structure (the memtable) and to an append-only log for safety. Nothing on disk changes. When the memtable reaches, say, 64 MB, it is written out as one immutable sorted file (an SSTable) in a single sequential write.
| After writing keys k1…k1000 | B-tree on disk | LSM on disk |
|---|---|---|
| state | 1,000 leaf pages touched, many random writes | one log append per key, then one 64 MB sorted file |
| read key k500 | walk the tree, one page read | check memtable, then the newest SSTable, then older ones |
Step 3: the LSM read path and its helpers. A key may be in any SSTable, so a read could touch many files. Two helpers keep that cheap: a Bloom filter per file says "definitely not in this file" without reading it, and a small index per file points to the right block.
Step 4: compaction. Over time there are many SSTables with overlapping keys and dead versions. A background compaction merges them, newest value wins, and writes a smaller set of files. This is the weekly sorting of the notebook. It costs disk bandwidth but keeps reads bounded.
Step 5: choose. Writes are sequential and batched in an LSM, so a disk that does 100 MB/s sequential but only 100 random writes a second can absorb 100,000 small writes a second instead of 100. B-trees pay a random write per change but give the simplest, most predictable reads and in-place updates.
Why it works, with the numbers
Disks and SSDs are far better at sequential than random access, and the LSM is built on that asymmetry:
LSM write throughput ≈ sequential bandwidth ÷ (record size × write amplification); with 100 MB/s, 100-byte records and amplification 10, about 100,000 writes/s
Write amplification is the price: each record is rewritten several times by compaction (often 10 to 30 times across levels). Read amplification is the other price: a read may check several files, bounded by the number of levels and almost eliminated for missing keys by Bloom filters. A B-tree has write amplification of about one page per write and read amplification of one path through the tree. The guarantee of both is sorted order on disk, which is what makes range scans ("all keys from a to b") possible in either. The failure modes are compaction falling behind under a write storm (reads slow, disk fills) for the LSM, and random-write saturation and page splits under heavy insert load for the B-tree.
The trade-off you must say out loud
LSM for write-heavy, append-mostly data with mostly point reads and recent-data scans: logs, metrics, messages, events. B-tree for read-heavy, update-in-place data with many range queries and transactions: accounts, inventory, user records. Say which workload you have and name the family: Bigtable, Cassandra, RocksDB and LevelDB are LSM; PostgreSQL, MySQL and most relational engines are B-tree. The follow-up is "what about compaction stalls?", and the answer is rate-limiting compaction and sizing disks for the extra bandwidth.
Where it shows up in the 100 Google problems
- Design a distributed key-value store: each node's local engine is an LSM so the cluster can absorb a write-heavy workload.
- Design Bigtable: the original LSM at scale: memtable, immutable SSTables, compaction, Bloom filters.
- Design a distributed search engine like Elasticsearch: index segments are immutable sorted files merged in the background, an LSM shape applied to an inverted index.