B-Tree vs LSM Tradeoffs

The two dominant storage-engine families have opposite shapes:

B-tree (Postgres, MySQL InnoDB, SQLite, BoltDB, etcd-via-BoltDB):

• A balanced on-disk tree of fixed-size pages (typically 4–16 KB).
• A write modifies a page in place (after writing the change to the WAL).
• One disk seek per page; tree height typically 3–4 for very large data.
• Reads: O(log n) page accesses.

LSM tree (LevelDB, RocksDB, Cassandra, ScyllaDB, the storage layer of CockroachDB / TiKV / FoundationDB):

• Writes go to an in-memory memtable + WAL; later flushed to sorted, immutable SSTables; compaction merges SSTables.
• Reads check the memtable + (potentially) multiple SSTables in newest-first order, gated by Bloom filters.

Read vs write amplification

Sequential vs random I/O is the original motivator: spinning disks are ~100x slower at random writes than sequential. SSDs narrowed this gap but it still exists, and SSDs die faster under random writes too. LSMs convert random writes into sequential appends + background sorted merges.

When to pick which

B-tree wins when:

• Reads dominate writes
• Range scans are common (especially indexed scans)
• You need strict serializable transactions (in-place pages make locking simpler)
• Working set fits well in the page cache

LSM wins when:

• Writes dominate (ingest-heavy workloads: time series, logs, metrics)
• Data is much larger than RAM (Bloom filters keep read amp manageable)
• You can tolerate the compaction "tax" (CPU + I/O) in the background

Hybrids exist: WiredTiger (MongoDB) lets you pick LSM or B-tree per collection. Postgres has experimental columnar/LSM extensions.

Concrete numbers (rough orders of magnitude)

• RocksDB write amplification with default leveled compaction: ~10–30x
• A 3-level B-tree on 1 TB of data: ~3 disk seeks per random GET (almost all of L1/L2 sits in page cache)
• Cassandra (size-tiered) read amplification: 5–10 SSTables per cold key without Bloom filters

A key insight from Mark Callaghan and the RocksDB team: the right metric is the product of read-amp × write-amp × space-amp, not any one in isolation. Different engines hit different points on the RUM (Read-Update-Memory) tradeoff triangle.