LSM trees vs B-trees: the three amplifications

What it is

Two ways to build an on-disk ordered index, with opposite trade-offs.

A B-tree (in practice a B+tree) keeps data sorted in fixed-size pages, updated in place. A write locates the page holding the key and rewrites it. Reads walk from the root down, typically three or four page reads for a large index, and the tree is maintained in sorted order at all times. This is what PostgreSQL, MySQL/InnoDB, Oracle and SQL Server use.

An LSM tree (Log-Structured Merge tree) never updates in place. Writes go to an in-memory sorted structure (the memtable); when it fills, it is flushed as an immutable sorted file (an SSTable) and a new memtable starts. Reads may have to check several SSTables. A background compaction process merges SSTables to bound the read cost and reclaim space. This is what RocksDB, LevelDB, Cassandra, ScyllaDB and HBase use, and what backs Flink's state and Kafka Streams' stores.

The three numbers that decide between them:

You cannot minimise all three. This is the RUM conjecture (Read, Update, Memory): optimising any two costs you the third, and every storage engine's configuration is a point on that surface. The engine choice picks a region; the tuning picks a point.

What they are confused with: "LSM is for writes and B-tree is for reads" is the folk version and it is too crude. A well-tuned LSM with bloom filters serves point reads in roughly one disk read, which is comparable to a B-tree. The real distinctions are range-scan behaviour, transactional integration, and which amplification you can afford.

The problem it solves

The B-tree's problem: a small write costs a page write. Update one 100-byte row and InnoDB writes a 16 KB page. That is 160x write amplification before you count the write-ahead log, and InnoDB additionally writes the page to a doublewrite buffer to survive torn pages, so the real figure can approach 320x for a random single-row update.

At scale that matters in two ways. SSD endurance: a drive rated for 3 drive-writes per day, receiving 300x amplified writes, reaches its endurance limit far sooner than the workload suggests. And random write throughput: B-tree updates scatter across the tree, so the disk sees random 16 KB writes, which even on NVMe is meaningfully slower than sequential.

The LSM's problem: a read may have to look in many places. A key could be in the memtable, or any of several SSTables, so a naive LSM read checks all of them. Bloom filters fix this for point lookups (they answer "definitely not here" cheaply) and do nothing for range scans, which must merge across every file whose key range overlaps.

And the LSM's other problem, which is the one that surprises people: compaction is not free. The background merging that keeps reads fast is itself write amplification, and it competes with foreground traffic for disk bandwidth. An LSM under sustained write load can enter a state where compaction cannot keep up, at which point the engine throttles or stalls writes deliberately, because the alternative is unbounded read amplification.

Mechanics

The B-tree write path

UPDATE users SET name='bob' WHERE id=4711;

1. Find the leaf page containing id=4711        (3-4 page reads, usually cached)
2. Write the change to the WAL                  (sequential, small, fsync'd)
3. Modify the page in the buffer pool           (in memory, marked dirty)
4. Later: checkpoint writes the page to disk    (random 16 KB write)
   (InnoDB: first to the doublewrite buffer, then in place: TWO writes)

Write amplification for one 100-byte row:

WAL record:              ~150 bytes
Doublewrite page:        16,384 bytes
In-place page write:     16,384 bytes
                        ─────────────
Total:                   ~32,900 bytes for 100 bytes of data  = ~330x

Page writes are amortised when many rows in the same page are updated before the checkpoint, which is why sequential-key inserts (an auto-increment primary key) amplify far less than random-key inserts (a UUID primary key). That difference is the single most consequential schema decision for B-tree write throughput, and it is why UUIDv7 (time-ordered) exists.

The LSM write path

PUT users/4711 = {...}

1. Append to the WAL                            (sequential, fsync'd)
2. Insert into the memtable                     (in-memory skip list; no disk)
   ... memtable reaches 64 MB ...
3. Flush memtable to an immutable SSTable       (one large SEQUENTIAL write)
4. Background: compaction merges SSTables       (large sequential reads and writes)

Steps 1 to 3 are cheap: the foreground write touches memory and a sequential log. All the cost is in step 4, deferred and batched.

The LSM read path, and the bloom filter

GET users/4711

1. Memtable                                     (in-memory, fast)
2. Immutable memtables awaiting flush           (in-memory)
3. Level 0 SSTables: check EVERY file           (L0 files have overlapping ranges)
4. Level 1..N: binary search for the ONE file per level whose range covers the key
5. For each candidate file:
     a. Check the bloom filter -> "definitely not here"? skip, no disk I/O
     b. Read the index block, then the data block

Bloom filters are what make LSM point reads competitive. A 10-bits-per-key filter has roughly a 1 percent false-positive rate, so checking 7 levels costs about 0.07 unnecessary block reads on average. Without them, a 7-level LSM would do 7 disk reads per lookup.

The important limitation: bloom filters do not help range scans. A filter answers "is key K present," and a scan asks "what keys are in [A, B)," which every overlapping file might contribute to. So a range scan merges across all of them, and range-scan performance is the LSM's genuine weakness relative to a B-tree, where a range scan follows the linked leaf pages in order.

Compaction strategy sets the amplification trade

Two strategies bracket the space; a third handles time-series. The full treatment is on compaction strategies; the summary here is what makes the amplification numbers concrete.

Leveled (LCS): each level holds non-overlapping files, each level roughly 10x the previous. A key exists in at most one file per level.

Write amplification:  ~10 per level x levels  ≈ 10-30x
Read amplification:   ~1 file per level  ≈ low
Space amplification:  ~1.1x  (very good)

Size-tiered (STCS): merge files of similar size when enough accumulate. Files at the same tier overlap.

Write amplification:  ~4-10x  (much lower)
Read amplification:   several files per tier  (higher)
Space amplification:  up to 2x during a major compaction, because the merge
                      writes a new copy before deleting the old

That 2x space amplification is a hard operational constraint: a size-tiered LSM holding 4 TB can need 8 TB free at the moment of a large compaction, and running out of disk mid-compaction is how a Cassandra node dies.

The full comparison

Sequential versus random write pattern is the underrated row. Even where an LSM's write amplification is numerically similar to a B-tree's, the LSM writes large sequential blocks, which SSD controllers handle far better: less internal garbage collection, less write amplification inside the drive, and better throughput. The disk-level amplification is a second multiplier that the engine-level number does not capture.

Tombstones: the delete problem

An LSM cannot delete in place, so a delete writes a tombstone, a marker that the key is gone. The tombstone must persist until every SSTable containing older values for that key has been compacted away, or the key would resurrect.

Two consequences. Deletes make things bigger before they make them smaller: a delete-heavy workload grows the dataset. And a range scan must read every tombstone in its range, so scanning a range where a million rows were deleted reads a million tombstones to return zero rows. That is the Cassandra range-scan timeout, covered on Cassandra tombstones, and it is the most common LSM production incident.

A worked example: 4x the SSD lifetime, and a range scan that got worse

A time-series metrics platform storing about 1.4 million points per second. Started on PostgreSQL, moved to a RocksDB-backed store, and the migration is a clean illustration of what each amplification actually costs.

On PostgreSQL (B-tree), measured over one week:

user data written:              4.7 TB
bytes written to SSD:           38.1 TB
write amplification:            8.1x        (helped by mostly-sequential timestamps)
p99 write latency:              14ms
p99 point read:                 0.9ms
p99 range scan (1h window):     11ms
SSD wear (DWPD consumed):       2.9 of 3.0 rated       <- the problem

The write amplification of 8.1x is good for a B-tree, because the primary key was time-ordered so inserts appended to the rightmost page rather than scattering. The problem was absolute volume: at 2.9 of 3.0 rated drive-writes per day, the SSDs would reach their endurance limit in about 14 months, against a 5-year hardware plan.

On RocksDB with leveled compaction:

user data written:              4.7 TB
bytes written to SSD:           21.6 TB
write amplification:            4.6x        (better, and SEQUENTIAL)
p99 write latency:              0.7ms       <- 20x better
p99 point read:                 1.1ms       (slightly worse, bloom filters working)
p99 range scan (1h window):     47ms        <- 4.3x WORSE
SSD wear (DWPD consumed):       1.6 of 3.0

Three results, and the third is the one that mattered to the product.

Writes got much better. The foreground write is a memtable insert plus a WAL append, so p99 write latency dropped from 14 ms to 0.7 ms. Engine-level amplification nearly halved, and because the writes are sequential the drive's internal amplification also fell, which is why measured SSD wear dropped by more than the engine number alone predicts.

Point reads were a wash, 0.9 ms to 1.1 ms. Bloom filters did their job.

Range scans got 4.3x worse, and range scans were the dominant query: every dashboard panel is a range scan over a time window. The cause was structural rather than a misconfiguration: a scan merges across every SSTable overlapping the range, and with leveled compaction at 7 levels that is up to 7 files, each contributing an iterator to a merge heap. A B-tree walks linked leaf pages.

The fix was to change compaction strategy to match the data's shape:

# Time-windowed compaction: files are grouped by time window and never
# merged across windows. A 1-hour scan touches the files for that hour only.
compaction_style = kCompactionStyleUniversal
# plus explicit time-based partitioning of column families by day

For genuinely time-series data, files that never mix time ranges mean a scan for [t, t+1h) opens the one or two files covering that hour, and every other file is excluded by its metadata without reading anything.

                        Postgres    RocksDB(leveled)   RocksDB(time-windowed)
p99 write latency         14ms          0.7ms              0.7ms
p99 point read            0.9ms         1.1ms              1.2ms
p99 range scan (1h)       11ms          47ms               6ms
write amplification       8.1x          4.6x               3.1x
SSD DWPD consumed         2.9           1.6                1.1
disk used (1.4 TB live)   1.9 TB        1.6 TB             1.5 TB

Range scans ended up better than PostgreSQL (6 ms against 11 ms), and write amplification fell further still, because time-windowed compaction rarely rewrites old data: a file from last Tuesday is merged once and then left alone, where leveled compaction rewrites data repeatedly as it descends the levels.

The general lesson is the useful one: the compaction strategy matters more than the LSM-versus-B-tree choice. The same engine, on the same hardware, with the same data, went from 4.3x worse than PostgreSQL at range scans to nearly 2x better, purely from matching compaction to the access pattern. Picking "an LSM" is the coarse decision; picking the compaction strategy is where the performance is.

The endurance number was what justified the project: 2.9 to 1.1 DWPD took projected drive life from about 14 months to over 4 years.

Production evidence

PostgreSQL and InnoDB are B-trees, and InnoDB's doublewrite buffer is a concrete instance of B-tree write amplification: to survive a torn 16 KB page write, it writes every page twice. innodb_doublewrite=0 is a real tuning option on filesystems with atomic writes, and the fact that it is a documented trade of durability against write volume tells you how much the amplification costs.

RocksDB grew out of LevelDB at Facebook for server workloads, and their published work is the reference material on the amplification trade. The RocksDB wiki documents measured write amplification per compaction style and the tuning guide is organised explicitly around which amplification you are willing to pay.

Cassandra defaults to size-tiered compaction and offers leveled and time-windowed, with documentation recommending leveled for read-heavy workloads with updates, and time-windowed for time series. Their guidance that STCS can need 50 percent free disk for a major compaction is the operational expression of size-tiered space amplification.

WiscKey (Lu et al., FAST 2016) separates keys from values so compaction rewrites only keys, cutting write amplification substantially for large values. It shipped as RocksDB's BlobDB and Titan, and is the main published refinement to the basic LSM design.

Facebook's MyRocks replaced InnoDB with RocksDB under MySQL for their user database and they published the comparison: roughly half the storage and substantially lower write amplification versus compressed InnoDB. That is the clearest apples-to-apples production comparison available, since it is the same application and query workload on two engines.

Modern B-tree engines borrow LSM ideas. InnoDB's change buffer defers secondary index updates by logging them and applying them later, which is a small LSM inside a B-tree, and it exists for exactly the random-write-amplification reason.

The debate

Which should you choose? Start from what your workload does most.

Choose a B-tree when: reads dominate, especially range scans; you need multi-key transactions and mature MVCC; predictable read latency matters more than peak write throughput; or the working set fits in memory, which makes the whole discussion mostly moot because writes are absorbed by the buffer pool.

Choose an LSM when: writes dominate; write latency must be low and predictable; you are on SSDs and endurance is a real cost; or you need good compression, which LSMs achieve more easily because SSTables are immutable and compressed in large blocks (a B-tree compresses per page, which is a much smaller compression window).

My position: for a general-purpose transactional application, use PostgreSQL and stop thinking about this. Its B-tree write amplification is a problem at a scale most applications never reach, and the transactional guarantees, the query planner and the tooling are worth far more than an amplification factor. Reach for an LSM when you have measured that write volume or SSD endurance is the constraint, or when you have chosen a distributed store (Cassandra, ScyllaDB) for reasons that have nothing to do with the index structure.

The trap I would push back on: choosing Cassandra "because we have a lot of writes" without checking the read pattern. If those reads are range scans over wide partitions, you have optimised the cheap half and made the expensive half worse, and adding tombstones from deletes or TTLs makes it worse again.

Is write amplification actually worth optimising? It depends on what binds. On cloud instances with network-attached storage (EBS, Persistent Disk), you are billed for provisioned IOPS and throughput, so amplification is directly money and the answer is yes. On local NVMe with a generous endurance rating and a workload well under it, the amplification is invisible and optimising it is wasted effort. Measure DWPD consumed and provisioned-IOPS utilisation before deciding it is a problem, because those two numbers turn an architectural debate into an arithmetic one.

Space amplification is the one people forget. The instinct is that LSMs are compact because SSTables compress well, and size-tiered compaction can use 2x the live data size at the moment of a major compaction. A B-tree at 70 percent fill factor with some fragmentation sits around 1.4x, steadily. If disk headroom is tight, leveled compaction (~1.1x) is the safest of the three and you pay for it in write amplification.

Follow-up Q&A

"What are the three amplifications and why can't you minimise all three?"

Write amplification is bytes written to disk per byte of user data; read amplification is disk reads per logical read; space amplification is disk used per byte of live data. The RUM conjecture says optimising any two costs you the third, and the LSM compaction strategies demonstrate it directly: leveled compaction gets excellent space amplification (~1.1x) and low read amplification by paying 10 to 30x write amplification; size-tiered gets write amplification down to 4 to 10x by accepting up to 2x space and higher read amplification. Same engine, same data, different point on the same surface.

"Why is a B-tree write so expensive?"

The unit of update is a page. Changing 100 bytes means writing a full 16 KB page, plus a WAL record, plus (in InnoDB) a doublewrite copy to survive a torn write: roughly 33 KB for 100 bytes. It amortises when many rows in the same page change before a checkpoint, which is why an auto-increment primary key amplifies far less than a random UUID: sequential keys concentrate updates in the rightmost pages, random keys scatter them across the whole tree so almost every page write carries one row's change.

"How does an LSM keep point reads fast with data in many files?"

Bloom filters. Each SSTable carries one, so a lookup asks "could this key be here" and gets a definite no cheaply. At 10 bits per key the false-positive rate is about 1 percent, so checking 7 levels costs roughly 0.07 unnecessary block reads on average. The levels above L0 also have non-overlapping key ranges, so at most one file per level is a candidate and it is found by binary search on file metadata rather than by scanning.

"Why are range scans worse on an LSM?"

Bloom filters cannot help. A filter answers "is key K present," and a scan asks "what is in [A, B)," which any overlapping file may contribute to. So the scan opens an iterator per overlapping file and merges them. A B-tree's leaves are linked in key order, so a scan reads sequentially. The mitigation is a compaction strategy that reduces overlap in the dimension you scan on: time-windowed compaction for time series took a range scan from 47 ms to 6 ms in the example above.

"An LSM is stalling writes. What is happening?"

Compaction cannot keep up with ingest, so the engine is deliberately throttling to prevent unbounded read amplification. In RocksDB the specific triggers are level0_slowdown_writes_trigger and level0_stop_writes_trigger: too many L0 files, because L0 files have overlapping ranges and every read must check all of them. The causes are compaction threads starved of I/O or CPU, a compaction strategy that amplifies more than the disk can absorb, or simply an ingest rate above what the hardware supports. The levers are more compaction threads, a lower-amplification strategy, a larger memtable to flush less often, or accepting a lower write rate. See RocksDB tuning.

"Which would you pick for a write-heavy service with range queries?"

I would want the numbers before answering, and the honest default is: if the ranges are over a naturally clustered dimension like time, an LSM with a matching compaction strategy, because you get the write benefit and the scan penalty largely disappears. If the ranges are over an arbitrary secondary dimension, a B-tree, because the LSM's scan penalty applies at every scan and the write benefit does not compensate. And if "write-heavy" turns out to mean 5,000 writes per second, PostgreSQL handles that on modest hardware and the whole question is premature.

Common misconceptions

"LSMs are for writes and B-trees are for reads." Too crude. LSM point reads with bloom filters are competitive with B-tree reads. The real distinction is range scans, where the B-tree's linked leaves beat merging across SSTables, and transactional maturity, where B-tree engines are far ahead.

"LSMs use less disk." Not necessarily. Size-tiered compaction can use up to 2x live data during a major compaction, and tombstones from deletes make the dataset grow before it shrinks. Leveled compaction is genuinely compact (~1.1x) and pays for it in write amplification.

"Compaction is background work, so it is free." It competes with foreground traffic for disk bandwidth, CPU and page cache, and when it falls behind the engine stalls writes deliberately. Compaction is a first-class capacity consideration, not a housekeeping detail.

"Write amplification only matters for SSD wear." It also consumes the disk bandwidth your foreground traffic needs, and on cloud storage with provisioned IOPS it is directly a bill. Those are usually the binding constraints before endurance is.

"Deleting data frees space immediately in an LSM." A delete writes a tombstone, which is more data. Space is reclaimed when compaction merges away every older value, which may be much later, and until then range scans over the deleted range still read every tombstone.

Interview delivery note

Say this verbatim: "The choice is which of the three amplifications you can afford. B-trees pay write amplification, up to 300x for a random single-row update, because the unit of update is a page. LSMs make writes sequential and cheap and pay for it in read amplification on range scans and in compaction competing with foreground traffic." Framing it as a three-way budget rather than "writes versus reads" is what signals you understand the trade rather than the slogan.

The senior-versus-staff separator is compaction strategy mattering more than the engine choice. A senior engineer explains LSM versus B-tree correctly. A staff engineer notes that the same RocksDB, on the same data, went from 4.3x worse than PostgreSQL at range scans to nearly 2x better purely by matching compaction to the access pattern, so "we chose an LSM" is the coarse decision and the strategy is where the performance actually lives.

The second signal is turning the debate into arithmetic: measure DWPD consumed and provisioned-IOPS utilisation before declaring write amplification a problem. Most teams argue about it without knowing whether it binds.

Further reading

• O'Neil, Cheng, Gawlick and O'Neil, "The Log-Structured Merge-Tree" (1996), the original paper.
• Athanassoulis et al., "Designing Access Methods: The RUM Conjecture" (EDBT 2016), for the read/update/memory trade stated formally.
• The RocksDB wiki on compaction styles and tuning, which documents measured amplification per style.
• Lu et al., "WiscKey: Separating Keys from Values in SSD-Conscious Storage" (FAST 2016), for key-value separation and the write-amplification reduction it buys.