Topic 6.5
B-Trees vs LSM Trees: How Storage Engines Trade Reads for Writes
In one line
B-trees keep sorted keys in fixed-size pages updated in place: log-scale lookups with a height of 3–4 levels for billions of keys, at the cost of random writes and page splits. LSM trees buffer writes in memory, flush sorted immutable files and merge them by compaction: fast sequential writes, with read amplification mitigated by Bloom filters. The choice is a trade between read, write and space amplification.
Think of it like this
Two ways to keep a phone book. The B-tree way keeps one sorted book and pencils each new name into the right page, occasionally splitting a page in two. The LSM way jots new names into a notebook, periodically types the notebook up as a sorted booklet, and every so often merges booklets into bigger ones.
Key ideas
- 01
B-tree: internal pages hold separator keys and child pointers; leaves hold keys and row pointers (or rows, in clustered indexes) and are linked for range scans. With ~200–400 keys per 8 KB page, 3 levels address ~10–60 million keys and 4 levels billions, so a lookup costs 3–4 page reads, most of them cached.
- 02
B-tree insert: find the leaf, insert; if full, split into two and push a separator up (possibly cascading). Delete marks entries; pages merge or are reused later. Random-key inserts touch random pages (the UUIDv4 problem).
- 03
LSM tree: writes go to the WAL and an in-memory memtable (sorted); a full memtable becomes immutable and is flushed as an SSTable. Reads check the memtable, then SSTables from newest to oldest, skipping files via per-file Bloom filters and key ranges. Compaction merges files, drops overwritten values and tombstones.
- 04
Amplification: write amplification (bytes written to disk per byte of data: B-tree page rewrites and WAL vs LSM compaction rewrites), read amplification (pages or files touched per read), space amplification (bloat or unmerged duplicates). Leveled compaction favours reads and space; size-tiered favours writes.
- 05
Who uses what: PostgreSQL, MySQL InnoDB, SQL Server and Oracle use B-trees; RocksDB (and MyRocks, CockroachDB via Pebble, TiKV), Cassandra, ScyllaDB, HBase and LevelDB use LSM trees. See the Bloom Filters course (Phase 5) for per-SSTable filters in depth.
Code & diagrams
CREATE EXTENSION pageinspect;
SELECT * FROM bt_metap('orders_pkey');
-- magic | version | root | level | fastroot | fastlevel | ...
-- 340322 | 4 | 412 | 2 | 412 | 2 |
-- level 2 = root + 1 internal level + leaves: 3 page reads for any of ~20M keys
SELECT pg_size_pretty(pg_relation_size('orders_pkey')); -- 428 MBInterview problem
The problem
Choose a storage engine for two workloads
(a) An IoT platform ingests 2M sensor readings/sec, queries recent readings per device, and keeps 90 days. (b) A banking core with 5K transfers/sec, complex queries, strict transactions and frequent point reads. Choose B-tree or LSM-based stores and justify with amplification.
When it breaks
Tombstone-heavy reads in an LSM store
What you see
A queue-like table in Cassandra deletes rows constantly; reads scan thousands of tombstones and time out (TombstoneOverwhelmingException).
Fix & prevent
Don't model queues in LSM stores; use time-bucketed partitions with TTL and time-window compaction so whole files expire.
Explain it without notes
Why do LSM trees have better write throughput than B-trees?
Practice
Estimate B-tree height for 2 billion 8-byte keys with ~350 entries per page.
Trade-offs
- ↔
B-trees: predictable reads, in-place updates, random-write cost. LSM: fast writes and compression, read and compaction overhead, and tombstones.
Done when you can
I can explain B-tree and LSM internals and pick an engine from read/write/space amplification.