Start here: two bets about writes#
TL;DRthe 30-second version
- Both engines store sorted data on disk and answer point lookups and range scans. They differ in one thing: what a write does. A B-tree overwrites the data in place; an LSM tree appends the write and merges it in later.
- That choice is a trade between three costs — read amplification (extra reads per lookup), write amplification (extra bytes written per byte of data), and space amplification (extra disk used per byte of live data).
- B-trees favour reads: a lookup is a few page reads down a shallow tree, and there's little wasted space. The cost is random writes and write amplification from rewriting whole pages.
- LSM trees favour writes: every write is a cheap sequential append, so they ingest huge write volumes. The cost is read amplification (a lookup may check several files) and background compaction work, softened by Bloom filters and merging.
Point at any database and ask how it stores a row on disk, and the answer is almost always one of two shapes. The first is the B-tree (specifically the B+ tree): a shallow, balanced tree of fixed-size pages that stays sorted, so any row or range is a handful of page reads away. The second is the LSM tree (log-structured merge-tree): writes are buffered in memory and flushed to disk as sorted files that pile up and get merged over time. Both are covered in depth in their own topics — this page is about choosing between them.
The fork is the write path. A B-tree does an update in place: to change a row, it reads the page that row lives on, modifies it, and writes that page back to the same spot on disk. An LSM tree does the opposite — it never overwrites; it appends the new value to an in-memory buffer, and that buffer is later flushed to disk as a new sorted file, leaving the old value to be dropped during a future merge. Update-in-place versus append-and-merge is the entire disagreement, and everything else is a consequence of it.
A quick recap of each engine#
The B+ tree keeps keys sorted in a balanced tree whose nodes are disk pages. Interior pages hold separator keys that route a lookup down to the leaf; leaf pages hold the data (or pointers to it) and are chained together for range scans. Because the tree is kept balanced and shallow, any key is found in a small, near-constant number of page reads. Updates modify a leaf page in place, splitting a page when it overflows. You can watch the tree grow and split in the B+ tree simulator (/btree/sim).
The LSM tree buffers writes in a sorted in-memory structure (the memtable). When the memtable fills, it's flushed to disk as an immutable sorted file called an SSTable. Writes keep coming, so SSTables accumulate; a background process called compaction merges them, keeping the newest value for each key and discarding older ones. A read checks the memtable first, then the SSTables from newest to oldest — using a Bloom filter per file to skip the ones that definitely don't contain the key. The LSM simulator (/lsm/sim) shows the flush-and-compact cycle step by step.
The three amplifications#
The whole comparison comes down to three ratios, each measuring waste relative to the ideal of touching exactly the data you asked for. They're the vocabulary interviewers use, so know them by name.
- Read amplification: how many disk reads it takes to answer one lookup. Ideal is one. A B-tree reads a few pages down the tree. An LSM read may probe the memtable plus several SSTables — higher, though Bloom filters cut out the files that can't hold the key.
- Write amplification: how many bytes actually get written to disk per byte of data you wrote. A B-tree rewrites a whole page (and the WAL) even for a tiny change. An LSM writes sequentially but rewrites data repeatedly during compaction, so a byte can be re-written several times over its life.
- Space amplification: how much disk is used per byte of live data. A B-tree is compact but leaves pages partially full (and fragmented). An LSM holds stale, superseded versions of keys until compaction removes them, so it can temporarily use extra space.
No engine wins all three — improving one usually worsens another. Compact an LSM more aggressively and you lower read and space amplification but raise write amplification (more merging). Pack a B-tree's pages fuller and you lower space amplification but raise write amplification (more splits). This is the RUM conjecture in miniature: you get to optimise for Reads, Updates, or Memory, but not all three at once.
| B-tree | LSM tree | |
|---|---|---|
| Write path | Update in place (random I/O) | Append + later merge (sequential I/O) |
| Read amplification | Low — a few pages down the tree | Higher — memtable + several SSTables (Bloom-filtered) |
| Write amplification | Higher — rewrite whole pages | Lower on ingest, but compaction rewrites data repeatedly |
| Space amplification | Low — but partially-full/fragmented pages | Higher — stale versions linger until compaction |
| Best at | Reads, point lookups, low latency | High write throughput, sequential ingest |
PredictYou're storing a firehose of time-series metrics: millions of writes per second, mostly appends, read back later in ranges. B-tree or LSM — and which amplification are you deliberately accepting?
Hint: Which engine makes writes a sequential append, and what does it cost you on reads?
LSM. A write-heavy, append-mostly workload is exactly what LSM is built for: every write is a cheap sequential append to the memtable, so it sustains write rates a B-tree can't, because a B-tree would be doing a random page rewrite (plus WAL) per write and thrashing the disk. The amplification you accept in return is read amplification (a lookup may touch several SSTables) and write amplification from compaction rewriting data — but for time-series that's fine: reads are ranged and less frequent, and Bloom filters plus the sorted, time-ordered SSTables keep range scans efficient. This is why time-series and write-heavy stores (Cassandra, RocksDB-backed systems, InfluxDB-style engines) are LSM, not B-tree. The one-line answer: trade read/write amplification for write throughput.
Matching the engine to the workload#
The decision is almost never about raw speed — it's about which amplification your workload can afford. A few rules of thumb that hold up in an interview:
- Write-heavy, ingest-dominated (logs, metrics, event streams, messaging): LSM. Sequential appends absorb write volume a B-tree can't match.
- Read-heavy with latency-sensitive point lookups (an OLTP row store, a secondary index you read constantly): B-tree. A lookup is a predictable few page reads with no compaction to compete with.
- Mixed read/write with strong consistency and transactions: B-tree is the traditional default (Postgres, InnoDB), because in-place updates map cleanly onto row locking and predictable latency.
- SSD lifetime and write cost matter: it's nuanced. LSM's sequential writes are gentler per write, but its compaction re-writes data repeatedly, so total bytes written can be high; B-trees write fewer total bytes but more randomly. Measure for your workload.
The honest interview answer is rarely 'LSM is faster' or 'B-trees are faster.' It's: name the dominant operation (ingest vs point-read), name the amplification you're willing to pay, and pick the engine whose bet matches. That framing shows you understand the trade, not just the trivia.
The decision, in one table#
| If your workload is… | Lean toward | Because |
|---|---|---|
| Write-heavy / append-mostly | LSM | Sequential appends sustain high write throughput |
| Read-heavy / point-lookup latency | B-tree | A lookup is a few predictable page reads, no compaction |
| Range scans over recent data | Either (edge to LSM) | Both keep data sorted; LSM's SSTables are written in time order |
| Tight tail latency (p99 = 99th percentile) | B-tree | LSM compaction can cause write stalls / latency spikes |
| Huge datasets, cheap ingest, some staleness OK | LSM | Lower write cost, space reclaimed lazily by compaction |
Modern engines blur the line — B-trees borrow LSM ideas (write buffering) and LSM engines add caching and smarter compaction strategies to tame read amplification — but the underlying bet still tells you what each is good at. When in doubt: write-bound reaches for LSM, read-bound and latency-bound reaches for B-tree.
In the wild
- B-tree engines: PostgreSQL and MySQL/InnoDB (the default row stores), SQLite, and most traditional relational databases — chosen for predictable read latency and transactional workloads.
- LSM engines: Cassandra, ScyllaDB, HBase, and Google Bigtable for wide-column write-heavy stores; RocksDB and LevelDB as embedded engines; InfluxDB and similar for time-series.
- RocksDB (an LSM library from Facebook, forked from Google's LevelDB) is the storage layer under a huge range of systems — CockroachDB, TiKV, Kafka Streams state stores — making LSM the de facto engine for new distributed databases.
- MyRocks is MySQL with its InnoDB B-tree engine swapped for RocksDB's LSM — the same database, re-bet for write-heavy workloads with lower space usage, a real-world demonstration that the choice is a pluggable trade.
Pitfalls & gotchas
Isn't LSM just strictly faster because writes are sequential?
Faster to write, not faster overall. LSM's cheap appends come at the cost of read amplification (a lookup may check several files) and background compaction that competes for disk and CPU. On a read-heavy, latency-sensitive workload a B-tree's few predictable page reads win. 'Faster' only means something once you say faster at what.
How does an LSM keep reads from getting slow as SSTables pile up?
Two mechanisms. A Bloom filter per SSTable answers 'is this key definitely not here?' cheaply, so a point lookup skips files that can't contain the key. And compaction continually merges SSTables, reducing how many a read must consult. Together they keep read amplification bounded even as write volume grows — but they cost background work.
What's a compaction (or write) stall?
In an LSM, if writes come in faster than compaction can merge SSTables, the backlog grows until the engine deliberately throttles or pauses writes to let compaction catch up. That shows up as latency spikes — a real operational gotcha for LSM under sustained heavy writes, and a reason latency-critical systems sometimes prefer B-trees.
Why does a B-tree have write amplification if it updates in place?
Because the unit of a write is a whole page, not a byte. Changing one row rewrites its entire page (often 4–16 KB) back to disk, plus a write-ahead log entry for durability, plus possible page splits when a page overflows. So a tiny logical change can mean several kilobytes physically written — that's the B-tree's write amplification, separate from LSM's compaction-driven kind.
QuizA team runs a latency-critical service where p99 read latency must stay flat, on a mostly read workload. They're choosing a storage engine. Which is the safer default, and what's the main risk they avoid?
- LSM — sequential writes keep everything fast.
- B-tree — reads are a few predictable page reads, and they avoid LSM compaction stalls that spike p99.
- Either — the storage engine doesn't affect read latency.
- LSM — Bloom filters make reads faster than a B-tree's.
Show answer
B-tree — reads are a few predictable page reads, and they avoid LSM compaction stalls that spike p99. — For a read-heavy, latency-critical service, a B-tree is the safer default. A point lookup is a small, predictable number of page reads with no background merging competing for I/O, so p99 stays flat. The main risk they avoid is LSM's compaction/write stalls: when an LSM's compaction falls behind, it throttles and reads contend with heavy background merging, causing latency spikes exactly when you can't afford them. LSM's sequential writes and Bloom filters are real advantages, but they optimise for write throughput and point-lookup filtering, not the flat read-latency this workload needs.
In an interview
This comparison is a favourite because it rewards understanding over memorization. Don't declare a winner — frame it as a trade decided by the workload, and anchor it on the three amplifications. That's the difference between reciting 'LSM is for writes' and actually being able to choose.
- State the core fork first: B-tree updates in place (random writes, low read amplification); LSM appends and merges (sequential writes, higher read amplification). Everything follows from that.
- Use the vocabulary: read, write, and space amplification — and note you can't minimise all three (the RUM trade-off).
- Match to workload: write-heavy/ingest → LSM; read-heavy/latency-sensitive → B-tree; strong-consistency OLTP → B-tree by tradition.
- Name the LSM read defenses (Bloom filters + compaction) and the LSM gotcha (compaction/write stalls hurting p99) — that nuance signals real understanding.
- Ground it in systems: Postgres/InnoDB are B-tree; Cassandra/RocksDB are LSM; MyRocks is InnoDB re-bet as LSM. Both sit on a write-ahead log for durability.
PredictAn interviewer says: 'We're on Postgres and our write throughput is maxing out on a high-ingest logging table, but our latency-critical user-facing queries are fine. What would you consider?' What's the strong answer?
Hint: Two workloads, opposite needs — do you pick one engine, or route each workload to the engine that fits?
Recognize that one database is serving two workloads with opposite needs, and don't force one engine on both. The logging table is write-heavy ingest — a perfect LSM fit — while the user-facing queries are read/latency-critical, where Postgres's B-tree already shines. So the move isn't 'switch Postgres to LSM' (that would risk the latency-critical reads); it's to move the high-ingest logging workload onto an LSM-based store (Cassandra, ClickHouse, a RocksDB-backed system, or a time-series database) and leave the transactional workload on the B-tree engine that's already serving it well. Frame it as matching each workload to the engine whose amplification trade it can afford: the log tolerates read amplification for write throughput, the user queries need the B-tree's flat read latency. Naming that you'd split the workloads rather than compromise one engine is what makes the answer strong.
References
- Designing Data-Intensive Applications, Ch. 3 — Kleppmann's side-by-side of B-trees and LSM trees, and the amplification trade-offs.
- The Log-Structured Merge-Tree (O'Neil et al., 1996) — The original LSM paper.
- Designing Access Methods: The RUM Conjecture — Why you can optimise Reads, Updates, or Memory — but not all three.
- RocksDB — Compaction & the LSM engine — How a production LSM handles compaction, read amplification, and stalls.
- PostgreSQL — Index Types (B-tree) — The B-tree as the default index in a mainstream relational database.
Ready to try it?
The simulator is a real, deterministic implementation — pick a scenario and step through it, scrubbing the timeline forward and backward through every change.