B-trees vs LSM-trees: where each storage engine pays the cost

B-trees and LSM-trees solve the same basic problem: they maintain an ordered index so a database can find a key and scan a range efficiently. The important difference is not whether work happens. It is when the engine does the work, how much it rewrites, and how predictable that cost is under load.

The same write, different timing

A B-tree applies an update to its tree pages soon after the write arrives. An LSM-tree accepts the write cheaply at first, then turns it into sorted files and merges those files later. Both designs are useful. They just move the cost to different moments.

B-TREE
write
  -> append to WAL
  -> update a tree page

LSM-TREE
write
  -> memtable
  -> immutable SSTable
  -> later compaction

In a B-tree, the write-ahead log protects the change before the relevant fixed-size page is overwritten. A page split can make one update touch more pages. In an LSM-tree, a write enters an in-memory table, becomes an immutable sorted table on disk, and is eventually merged with older sorted tables.

Write amplification is the hidden cost

Write amplification means that one logical database write creates several physical writes on disk over its lifetime. It matters because write-heavy systems eventually run into a disk-bandwidth limit, and because extra writes also use SSD endurance.

A B-tree normally writes the WAL and the changed tree page. A small update can still rewrite a whole page, a split may write several pages, and some implementations write a page twice to guard against partial page writes after a power failure.

An LSM-tree has its own write amplification. Every compaction reads and rewrites sorted data as files merge. The engine may accept the original write quickly, but the work returns later as background maintenance.

one logical write
  -> WAL + page rewrite      (B-tree)
  -> flush + repeated merges (LSM-tree)

more physical bytes written
  -> less sustainable write throughput

Why LSM-trees often suit write-heavy workloads

LSM-trees often achieve higher write throughput because their SSTables are written sequentially and compaction also produces sequential output. That pattern is especially helpful on hard disks, where sequential writing is much cheaper than several random page overwrites.

They also tend to use disk space well. Sorted tables can be compressed, and compaction removes old versions and fragmentation. B-trees can leave unused space behind after page splits or when a row no longer fits on its original page.

This is a tendency, not a promise. Compaction strategy, workload shape, storage hardware, and configuration can all change the result. SSD firmware already uses log-structured techniques internally, so the hardware gap is narrower there, even though lower write amplification and compact data still help.

Compaction can turn into operational debt

Compaction competes with incoming writes and memtable flushes for the same disk bandwidth. A new or small LSM-tree can look extremely fast because little historical data exists to merge. The cost becomes clearer as the database grows.

disk bandwidth
  -> incoming writes
  -> memtable flushes
  -> compaction

if compaction falls behind
  -> more segments, slower reads, less free disk

If compaction cannot keep up, unmerged files accumulate. Reads must examine more segments, disk consumption rises, and the database can eventually run out of space. Many LSM implementations do not automatically slow incoming writes enough to prevent this, so a production system needs explicit monitoring of compaction backlog and free disk space.

Predictability matters as much as average speed

LSM compaction can have a small effect on average latency and throughput while still creating much worse tail latency. The p95 or p99 request may collide with a large merge, or it may need to search more files while the system catches up.

B-trees often behave more predictably because each key lives in one place in the tree and an update happens near the write. That does not make every B-tree fast, but it makes the work easier to reason about when latency must stay stable.

Why B-trees still fit transactional databases

A B-tree keeps one current copy of a key in the index. An LSM-tree can have versions of the same key across several sorted segments until compaction removes the older ones. This difference matters for isolation mechanisms that lock a range of keys. A relational database can attach those locks directly to the B-tree index.

B-trees are also mature, well understood, and consistently capable. That makes them a strong default when a system needs transactional behavior and predictable operational characteristics.

How I would decide

Mostly high writes, compact storage, and range scans
  -> test an LSM-tree

Tight tail-latency targets or range locking
  -> test a B-tree

Always
  -> benchmark at steady state
  -> monitor compaction and free disk

The workload decides. Measure real reads, writes, range scans, data size, latency targets, and failure behavior. A benchmark that only measures an empty database can hide the long-term cost of compaction.

What I will carry forward

The useful mental model is that storage engines do not remove work. B-trees pay more of it during each write through page updates. LSM-trees postpone more of it into compaction. I would choose based on where the application can safely absorb that cost, then verify the choice with a realistic workload.

These are my personal learning notes from Designing Data-Intensive Applications by Martin Kleppmann.