Every database you use is a B-tree or an LSM tree underneath. PostgreSQL and MySQL’s InnoDB are B-trees. RocksDB, Cassandra, ScyllaDB, and every write-optimized time-series store are LSM trees. The choice sounds academic until you are debugging a write stall at 2 a.m. because your LSM-based database decided to compact four levels at once, or watching a B-tree database do random I/O across the whole buffer pool to update one indexed column. These two data structures embody opposite bets about storage, and understanding them tells you most of what you need to know about how your database will behave under load.
This post walks through both structures from the storage engineer’s view: the mechanics, the amortized costs, the failure modes that show up in production, and the hybrid designs that increasingly dominate modern engines.
The B-Tree: Durable Reads in Place
A B-tree stores your data in place, in sorted order, in fixed-size pages — 8 KB in PostgreSQL, 16 KB in InnoDB. Lookups descend from the root through interior nodes, each holding sorted keys and child pointers, down to a leaf page that holds the actual rows. With fanout of a few hundred per node, a table with a billion rows is three to four levels deep. That is the entire magic: a lookup touches three to four pages, and the top levels are hot in memory, so a well-cached B-tree read costs one or two disk accesses.
The cost is on the write path. Updating a leaf page means a read-modify-write to a specific disk location. Database engines make that safe through a write-ahead log: every change is first appended to WAL, which is sequential and cheap, then applied to the page. But pages themselves are updated in place, so a B-tree pays a random write per modified page, plus WAL. A page split — inserting into a full leaf — amplifies this by splitting the page and inserting a key into the parent, occasionally cascading upward.
The B-tree read/write trade is therefore: fast, predictable point reads; moderate writes; and one unavoidable property — every read sees the most recent committed write, because there is only ever one copy of a row. For workloads dominated by reads with indexed access patterns, that is hard to beat.
The LSM Tree: Sequential Writes Above All
An LSM tree makes the opposite bet: never write in place, ever. Writes land in an in-memory memtable. When the memtable fills, it is flushed to disk as an immutable SSTable — a sorted string table. Older data lives in progressively deeper levels, each roughly an order of magnitude larger than the one above. A lookup checks the memtable, then level 0, then level 1, and so on, because a key can legally exist in multiple levels at once: newer versions shadow older ones until compaction removes them.
That shadowing is why LSMs need tombstones. A delete cannot physically remove data from immutable files, so it writes a marker that suppresses the shadowed versions during reads and is garbage-collected during compaction. Misses are the worst case: to prove a key does not exist, the engine must check every level, and Bloom filters are what keep this from being catastrophic — each level’s filter answers “definitely not here” with a few bits per key, so a miss usually touches filters instead of files.
Compaction is the background process that merges levels, physically drops shadowed versions and tombstones, and rewrites data into the next level. It is both the LSM’s superpower — turning random writes into large sequential ones — and its most dangerous component. The classic analysis frames this as the write amplification problem: an LSM with tiered compaction may rewrite the same data many times over its life across levels, so one logical write of 1 KB can mean tens of KB of physical I/O spread across background compaction threads.
Write Amplification vs Read Amplification
Every storage engine trades between three amplification factors: how much extra you write, how much extra you read, and how much space overhead you tolerate. The B-tree and LSM sit at different corners of this triangle.
- B-tree: moderate write amplification (WAL plus page updates, plus a full-page image per change in engines that snapshot pages), low read amplification (one page per lookup, no duplicates), moderate space overhead (page fill factors of roughly 70 percent after splits).
- LSM tree: high write amplification (compaction rewrites data repeatedly), higher read amplification (checks across levels; Bloom filters mitigate but do not eliminate), low space overhead per copy but transient duplication until compaction catches up.
The practical consequence: a B-tree’s cost is paid synchronously in the transaction path, while an LSM’s cost is deferred into background compaction. That difference defines their production personalities. The B-tree degrades smoothly — as data grows past the buffer pool, reads pick up more disk hits and latency creeps up. The LSM is fast and flat, then suddenly not: when compaction falls behind ingress, level 0 accumulates, read amplification spikes, and the engine enters the stall regime every operator learns to dread.
The Compaction Stall, Explained
A compaction stall is not a mysterious bug; it is arithmetic. Compaction throughput is bounded by disk bandwidth. If your write rate requires 200 MB/s of compaction work and the disk can give background threads 150 MB/s sustained (because foreground traffic is taking the rest), the backlog grows unboundedly. Memtables keep flushing, level 0 piles up, each read checks more overlapping files, and p99 latency climbs until writes are throttled or the disk saturates.
The mitigation levers, in rough order of effectiveness:
- Provision IOPS for compaction, not for foreground load. Budget peak ingress multiplied by your engine’s write amplification factor, then add headroom.
- Rate-limit ingest at the application. Many production incidents are fixed by capping write throughput below the compaction budget rather than buying bigger disks.
- Tune compaction style. Leveled compaction lowers read amplification and space use at the price of higher write amplification; tiered (size-tiered) does the opposite. Write-heavy append workloads often do better with tiered; read-heavy ones need leveled.
- Watch compaction backlog as an SLO. Pending compaction bytes is the leading indicator; p99 latency is a lagging one.
B-trees have stalls too — checkpoints that flush dirty pages, vacuum pressure in PostgreSQL, page splits on monotonically increasing keys — but they are bounded and predictable in a way LSM stalls historically have not been.
What Real Engines Actually Do
The clean dichotomy dissolves in production engines, which all cheat toward the middle.
RocksDB — the LSM implementation embedded in hundreds of production systems — added calibrated deletes, blob compaction for large values, and tunable level structures precisely because raw LSM behavior is unsuitable for many workloads. Cassandra and ScyllaDB expose compaction strategy as a per-table decision, because a metrics table and a user-profile table in the same cluster want opposite compaction styles. ScyllaDB’s whole engineering thesis is that a better scheduler around the same LSM structure (sharing-memory and shard-per-core design) tames the stall problem.
Meanwhile B-tree engines adopt LSM ideas. PostgreSQL’s unlogged tables and the pending-insert optimization in other engines buffer writes before touching the tree. And hybrid engines make the split explicit: many modern time-series and analytical systems use an LSM-style write path (memtable plus immutable segments) but with compaction policies specialized for time-ordered data, where compaction is trivially cheap because data arrives pre-sorted and old segments never change.
The design space also contains structures that reject both. Bitcask (the storage engine behind Riak) is a pure in-memory index over an append-only log — the logical extreme of the LSM bet, workable when the full key space fits in RAM. And Bepsilon trees sit between B-trees and LSMs with smaller node buffers, trading slightly worse reads for much better write amplification on some workloads.
Choosing in Practice
Frame the decision around four workload questions:
- What is the read/write ratio? Read-mostly with indexed lookups favors B-trees. Write-heavy ingest favors LSMs.
- Are keys append-shaped or random? Time-series and queue-like workloads with monotonically increasing keys are the LSM sweet spot — compaction is cheap and cache-friendly. Random keys across a huge space increase LSM read amplification and favor B-trees.
- Do you need strict read-after-write consistency per key? B-trees give it for free; LSMs give it too (reads check the memtable first), but scan-heavy reads over recently written data suffer from range fragmentation until compaction.
- Can you provision and monitor background I/O? LSMs require operational investment in compaction metrics. If you cannot watch that, a B-tree engine’s predictable degradation is safer.
For Cassandra/ScyllaDB-style deployments, per-table compaction strategy is the main tuning axis: TimeWindowCompactionStrategy for time-series, LeveledCompactionStrategy for read-heavy tables with random keys, and SizeTieredCompactionStrategy only for write-heavy tables with uniform access. For PostgreSQL, the equivalent decision is usually about index choice and table partitioning rather than storage engine — but the same arithmetic applies, which is why write-heavy Postgres deployments often offload history tables to an LSM-based store rather than fight autovacuum.
Wrapping Up
B-trees bet on fast reads and pay with in-place random writes; LSM trees bet on sequential writes and pay with compaction. Neither dominates — your workload’s read/write ratio, key distribution, and operational maturity decide which trade is cheaper. When you evaluate a database, look past the marketing and find out which structure it uses and what the engine does to patch that structure’s weaknesses. Those patches — Bloom filters, leveled vs tiered compaction, page-level write combining — are where the real engineering lives, and they explain the production behavior that benchmarks hide.