B-tree against LSM tree

The problem it solves

“Why did you choose Cassandra over Postgres?” is a question about storage engines, and the honest answer has nothing to do with which is faster. Both are fast. They pay for speed in different places, and the choice is about which bill you would rather receive.

A B-tree keeps data sorted in place. A write must find the page holding the key, read it, modify it, and write it back — a random read followed by a random write, for every update. An LSM tree never modifies anything in place. A write appends to an in-memory table and, eventually, to a new immutable file on disk. Writes are sequential and cheap; the cost is deferred, and it arrives later as compaction.

The mechanism

B-tree. A balanced tree of fixed-size pages, typically 4–16 KB, with a depth of three or four for realistic datasets. A read is one page read per level, and the upper levels are almost always cached, so a point lookup is usually one physical read. A write is a page read, a modify, and a page write — plus a write-ahead log entry for durability, which means the data is physically written twice. Because a whole page is rewritten to change one row, a 1 KB update to an 8 KB page costs 8 KB of write plus the WAL: write amplification of around 9×, before any index maintenance.

LSM tree. Writes go to an in-memory memtable, backed by a WAL. When the memtable fills it is flushed as an immutable sorted file (an SSTable) at level 0. Background compaction merges files from level to level, each level typically ten times larger than the last. A write is therefore a memory operation plus a sequential append — extremely cheap at the moment it happens. But each byte is rewritten once per level it descends through, so a five-level LSM has a write amplification of roughly the level count times the fan-out factor’s efficiency — commonly 10–30× in total, paid in the background.

Reads invert the comparison. A B-tree read touches one path. An LSM read may have to check the memtable, then every level, because the key could be in any of them. That is read amplification, and it is what Bloom filters exist to remove: a per-file filter that answers “definitely not here” cheaply, so a lookup touches one file instead of all of them. See Bloom filters.

What the simulation shows

The same workload runs through both engines with the amplification factors measured rather than asserted.

Start with the write comparison: an LSM write is an append to memory, a B-tree write is a random page read, a modify and a page write, and the gap at the moment of writing is more than an order of magnitude. That is the headline and it is real.

Then look at the read-p99 panel over time under the LSM engine. The spikes are compactions. Compaction competes with foreground reads for the same device — same IOPS, same bandwidth — and during one, the read p99 is many times the median. The LSM bill arrives later, in the tail. That is the operational story that decides most real architecture choices, and it is invisible in any benchmark that reports averages.

Now turn Bloom filters off. Read amplification jumps: every lookup must check every level. Turn them back on and almost every lookup touches one file. Bloom filters are not an optimisation on an LSM, they are load-bearing.

Compare against the B-tree: steadier reads, no compaction spikes, and a write amplification panel that is far from 1× — B-trees are not free of amplification either, and the page-rewrite arithmetic is on screen.

The numbers worth carrying

• B-tree write amplification: page size ÷ row size, plus the WAL. An 8 KB page and a 1 KB row is about 9×.
• LSM write amplification: roughly levels × fan-out efficiency; 10–30× is the usual range for level-tiered compaction, and size-tiered trades write amplification down for space amplification up.
• LSM read amplification without Bloom filters: up to one file check per level per lookup. With them, close to one.
• Space amplification: LSM holds obsolete versions until compaction reclaims them, so 1.1–2× the logical size is normal, and size-tiered compaction can transiently need twice the free space of the data being merged.

The rule of thumb worth carrying into a design discussion: write-heavy, append-mostly, tolerant of tail spikes → LSM. Read-heavy, update-in-place, latency-sensitive at the p99 → B-tree.

Where it breaks down

Compaction throttling is a real dial with a real trade. Throttle it and foreground latency improves while the level count grows, which raises read amplification and space usage; eventually the system falls behind and you get a much worse spike later. Do not throttle without watching the level count.

Range scans favour B-trees, since data is already ordered on disk. An LSM must merge across levels, and its scans are correspondingly more expensive.

Modern engines blur the line. Postgres’s heap plus indexes is not a pure B-tree story — HOT updates avoid index writes, and MVCC means old row versions need vacuuming, which is a compaction by another name with the same operational character. InnoDB’s change buffer defers secondary index maintenance, which is an LSM-ish idea inside a B-tree engine.

Hardware moves the answer. The LSM’s advantage was largest on spinning disks, where random writes were catastrophic. On NVMe, random writes are cheap enough that the gap narrows — though write amplification still consumes device endurance, and flash has a finite number of program-erase cycles, so amplification is a hardware-lifetime cost as well as a performance one.

What people get wrong

“LSM is faster.” At writing, at the moment of the write. Overall throughput depends on whether compaction can keep up with your write rate, and if it cannot, the system degrades badly.

“B-trees do not amplify.” Nine times, typically, for a small row. The simulation puts the number on screen.

“Compaction happens in the background so it is free.” It shares your disk. The read p99 panel is the argument.

“Bloom filters are an optimisation.” Remove them and watch read amplification. They are structural.

In production

RocksDB, LevelDB, Cassandra, ScyllaDB, HBase and the storage layer of CockroachDB and TiDB are LSM. Postgres, MySQL’s InnoDB, SQLite, and most classical relational engines are B-tree. MongoDB’s WiredTiger supports both. RocksDB’s tuning guide is essentially a document about choosing your amplification trade-offs, and its three knobs — write, read, space amplification — are called out as the RUM conjecture: you may optimise two, and the third gets worse.

Operationally, the metrics to watch differ. For an LSM: pending compaction bytes, level counts, and read p99 during compaction. For a B-tree: buffer-pool hit ratio, checkpoint behaviour, and index bloat. Alerting on the wrong set for your engine is a common way to be surprised.

The follow-up questions

“Why Cassandra over Postgres?” — Write throughput and horizontal partitioning, and be ready to say what it costs: compaction tails, read amplification, and no cross-partition transactions.

“What is write amplification and what is yours?” — Define it, then give both engines’ numbers.

“What happens during compaction?” — Foreground reads contend for the same device; p99 rises. Then say what you do about it: throttling, scheduling, or separate devices.

“Your workload is 95% reads of individual keys. Which engine?” — Either, honestly — with the LSM’s Bloom filters doing the work. The differentiator is the write rate and the tail requirement, so ask about those.