Deep Dive
high level designdistributed systemsdatabasesstorage

Storage Engines: LSM-Trees vs B-Trees

Every database makes one foundational choice — how to lay bytes on disk. B-trees update in place; LSM-trees never overwrite, they append and compact. That single decision sets your write throughput, read latency, and space usage. Drive an LSM write path — memtable, flush, compaction — and see the tradeoff for yourself.

·14 min read
Hard
Asked atGoogleMetaAmazonNetflixUberCloudflare

Two databases can speak identical SQL and behave completely differently under load — because underneath, they made opposite choices about one question: when you write a row, where do the bytes actually go? A B-tree finds the right page and overwrites it in place. An LSM-tree refuses to overwrite anything — it appends the write to memory, and later rewrites whole files in the background. That one difference is why Postgres and Cassandra have such different performance shapes.

The LSM write path is the one worth seeing, because it moves. Write keys and watch them collect in the in-memory memtable; when it fills, it flushes to an immutable file (SSTable); as files pile up, compaction merges them. Then read a key and watch how many layers it has to probe.

Memtablein-RAM · sorted · mutable
—
L0 · 0 SSTableson-disk · immutable · newest-first
—
L1 · emptyon-disk · compacted · no duplicates
—
Read a key
SSTables written0
Read amplificationup to 1 probes

Writes are cheap (append to RAM). Reads pay for it — more un-compacted L0 SSTables mean more probes. Compact to collapse them.

  • Empty engine. Writes land in the in-memory memtable first.

The whole story in one contrast

random writesequentialWrite (B-tree)find leaf → overwrite pageB-tree on diskmutable pages, in placeWrite (LSM)append to memtable + WALMemtable → SSTablesimmutable; flush + compactThe tradeoffB-tree: read-optimized · LSM: write-optimized
B-tree: a write seeks to the leaf page that owns the key and mutates it in place — great for reads and range scans, but every write is a random-access page update. LSM: a write only appends to an in-RAM memtable (plus a WAL); data reaches disk in large sequential flushes, and background compaction merges files. Writes are cheap and sequential; reads may consult several files (bloom filters keep that cheap).

Why you should care which one you’re running

  • Write throughput. LSM turns random writes into sequential appends + batched flushes, so it absorbs far higher write rates. If your workload is ingest-heavy (time-series, event logs, messaging), that’s decisive.
  • Read latency & range scans. A B-tree read is a single top-down traversal to one page; an LSM read may check several files. For read-heavy and range-scan workloads, B-trees are often simpler and more predictable.
  • Space & background work. LSM compaction reclaims space from overwritten/deleted keys but spends I/O rewriting data (write amplification) and can cause latency spikes. B-trees fragment and carry a write-ahead log, but have no compaction storms.

The members-only deep-dive builds both engines properly: the B-tree page model and why it’s read-optimized; the full LSM machinery (WAL, memtable, SSTables, the layered read with bloom filters, and compaction); the read/write/space amplification tradeoff and the RUM conjecture that says you can’t win all three; size-tiered vs leveled compaction (Cassandra vs RocksDB); a decision guide for which engine fits which workload; and how RocksDB, InnoDB, Postgres, and Cassandra/ScyllaDB actually ship this — with an interview challenge and quiz.

Members only

Keep reading with Premium

You've reached the members-only part of this deep-dive — the full implementation, the interactive ring simulator, and the step-by-step walkthrough. Unlock it with a membership.

Go PremiumAlready a member? Sign in