Part 3 · 1 chapters · ~8 min
B-Trees and LSM Trees, Side by Side
Why databases need disk-friendly trees, B+trees with high fanout and their page splits (MySQL and Postgres courses), LSM trees and compaction (NoSQL course), read, write and space amplification compared, where each wins, and engines that blend them.
4
Two families of storage engine
| B+tree | LSM tree | |
|---|---|---|
| write path | update the page in place (via WAL and buffer pool) | append to log + memtable; flush sorted files |
| read path | root to leaf: about 3-4 page reads for billions of rows | memtable, then SSTables newest first, Bloom filters to skip |
| write amplification | page writes per small change (plus full-page images) | rewritten during compaction (often 10× or more with leveled) |
| read amplification | low | higher, reduced by Bloom filters and compaction |
| space | fragmentation from splits and deletes | old versions until compacted |
| used by | InnoDB, Postgres, SQLite, WiredTiger (default), LMDB | RocksDB, Cassandra, ScyllaDB, LevelDB, Pebble, Kafka Streams stores |
| best for | read-heavy, point and range queries, transactions | write-heavy, time series, large ingest |
code
B+tree height: with 16 KB pages holding ~500 keys per internal node, height 3 → 500^3 = 125 million leaf pointers; height 4 → 62.5 billion. Every lookup is ≤ 4 page reads, mostly cached.