Storage Engines — B-trees vs LSM-trees

Start from the disk

One fact drives everything: sequential writes are enormously faster than random ones. On a spinning disk it's the seek — 8 ms versus effectively zero. On an SSD there's no seek, but random writes still cost more, because the drive erases in large blocks and must relocate and garbage-collect data behind your back.

So the fastest possible database is an append-only log. Writing is just "add to the end."

The problem is reading. To find a key you scan the entire log. Both designs below are answers to the same question: how do you keep append-friendly writes without ruining reads?

B-trees: keep the data sorted, always

A B-tree stores data in fixed-size pages (typically 4–16 KB), arranged in a balanced tree sorted by key. Each page holds many keys and pointers to child pages, so the branching factor is large and the tree is shallow.

The depth math is worth internalising. With ~500 keys per page:

1 page      →        500 keys
2 levels    →    250,000 keys
3 levels    → 125,000,000 keys
4 levels    →  62,500,000,000 keys

Any key in a 62-billion-row table is 4 page reads away — and the top levels are almost always in memory, so it's usually 1–2 actual disk reads. That's the property that made B-trees dominant for fifty years.

Writes update pages in place. Change one row, rewrite the whole page. If the page is full, split it — which rewrites two pages and updates the parent, possibly cascading upward.

Because a split touching several pages isn't atomic on disk, B-tree databases need a write-ahead log: append the intended change to a sequential log and fsync it, then modify pages. On crash, replay the WAL. This is why your writes are durable, and also why every write is written at least twice.

The B-tree bill: a single-row update can cost a WAL append plus a full 8 KB page write plus, occasionally, splits. Write ~100 bytes, write ~16 KB to disk. That ratio is write amplification, and it's why B-trees cap out at moderate write throughput.

LSM-trees: never update, only append and merge

Log-Structured Merge trees invert the design.

1. Writes go to an in-memory sorted structure, the memtable (plus a WAL for durability). The write is now complete. It was a memory operation.
2. When the memtable fills, it's flushed to disk as an immutable sorted file — an SSTable — in one sequential write.
3. Because SSTables are never modified, they accumulate. A background compaction process merges them, discarding overwritten and deleted entries.

Reads are the hard part: a key might be in the memtable, or any SSTable. Mitigations:

• Bloom filters per SSTable — a compact probabilistic structure answering "definitely not here" or "possibly here." One small memory lookup skips most files. Reads for non-existent keys become nearly free, which is exactly the workload that hurts otherwise.
• Sparse indexes — an in-memory index of every Nth key, so a read scans a small block.
• Levelled compaction — organise SSTables into levels with non-overlapping key ranges, so a read checks at most one file per level.

Deletes write a tombstone — a marker saying "this key is gone" — which is only truly removed when compaction has passed it through every level. A workload that writes and deletes heavily can accumulate tombstones and get slower at reading nothing, which is a genuinely confusing production experience.

The three amplifications

The vocabulary that makes this comparison precise:

• Write amplification — bytes written to disk ÷ bytes written by the application.
• Read amplification — disk reads per logical read.
• Space amplification — disk space used ÷ live data size.

You cannot minimise all three. This is the RUM conjecture (Read, Update, Memory: optimise for two, concede the third), and it's the real reason storage engines differ.

Note the crucial nuance: levelled LSM write amplification is often numerically similar to a B-tree's. The advantage isn't fewer bytes — it's that they're written sequentially, in large batches, in the background, rather than randomly on the request path.

Who uses what

Postgres is a partial exception worth knowing: rather than updating in place, it writes a new row version and marks the old one dead (MVCC — see the transactions lesson). That avoids some in-place update costs but creates bloat, requiring VACUUM to reclaim space. Different mechanism, same fundamental tradeoff.

What this means when you're designing

• Write-heavy, time-series-shaped, mostly-recent reads → LSM. Metrics, events, feeds, message history.
• Read-heavy, complex queries, joins, strict latency SLOs → B-tree. Anything transactional.
• Heavy overwrite or delete of the same keys → be careful with LSM; tombstones and compaction debt accumulate.
• Range scans over sorted keys → both work, B-trees more consistently.

And a practical warning: LSM databases need disk headroom and IO budget for compaction. Sizing an LSM cluster at 90% disk usage means compaction cannot run, and the system spirals. Plan for roughly 50% headroom.

What to take away

• Sequential writes beat random ones; every storage engine is a strategy for exploiting that.
• B-trees: sorted pages updated in place, shallow tree, WAL for crash safety, excellent and predictable reads, moderate write throughput.
• LSM: memtable → immutable SSTables → background compaction. Very fast writes, Bloom filters to rescue reads, tombstones for deletes, compaction-driven tail latency.
• Write/read/space amplification are the three axes, and you can only optimise two.
• LSM's win isn't fewer bytes written, it's writing them sequentially and off the request path.
• Give LSM systems real disk headroom, or compaction will not be able to save you.