Write, Read and Space Amplification

Definition: WA = bytes physically written to storage ÷ bytes logically written by the application, measured over a long enough window to include the deferred work. The deferred work is the point: an LSM tree's write path writes each byte once to the WAL and once at flush, and *then* compaction rewrites it once per level it passes through. With leveled compaction and size ratio T = 10, merging one file from level N into level N+1 rewrites on average (T+1)/2 ≈ 5.5 bytes of level N+1 per byte moved, so a byte that ends in level 4 has cost roughly 2 + 3 × 5.5 ≈ 18.5 bytes of writes. Tiered compaction merges equals with equals — about one rewrite per tier — for 2 + (L−1) ≈ 5.

A B+ tree has no compaction, but its unit of writing is the page. A 100-byte row that dirties an 8 KB page will, at the next checkpoint, cause an 8 KB write plus the WAL record — 83× if that row was the only change on the page. If sixteen rows on the page changed first, the page write is shared and the amplification is ≈ 6×. This is why B+ trees love sequential inserts (every insert lands on the same rightmost leaf) and hate random updates. It is also why "write amplification" appears in the practical Why Is This Query Slow? Indexes lesson: each secondary index is another tree, another page per row.

Definition: RA = physical pages or blocks read ÷ logical reads, distinguished by read type. A point read in a B+ tree is height + 1 pages, but the root and branch pages of any hot index live permanently in the buffer pool, so the uncached cost is ≈ 1 leaf page (plus the heap page in PostgreSQL). In an LSM tree a point read consults the memtable, every L0 file and one file per deeper level; each consultation is a bloom-filter check, and only a "maybe" costs a block read. With F candidate files and false-positive rate FP the expected block reads are ≈ 1 + (F − 1) × FP for an existing key and ≈ F × FP for an absent one — the filter is what makes the LSM read path competitive.

A range read gets no help from bloom filters. The B+ tree walks the leaf chain: one sorted run, sequential I/O. The LSM tree must open every run whose key range intersects the query and merge them, skipping tombstones: L0 + (L − 1) runs for leveled, up to (T − 1) × L for tiered. This asymmetry is the single most important line in the Storage Engine Comparison: B+ Tree vs LSM Tree comparison.

Definition: SA = bytes on disk ÷ bytes of live data. In an LSM tree the excess is stale versions and tombstones waiting for compaction. Leveled compaction bounds it tightly: the newest version of every key in level N shadows at most one copy in level N+1, and level N is 1/T of N+1, so SA ≈ 1 + 1/T ≈ 1.1. Tiered compaction lets the same key live in every run of a tier until the tier is merged, so with an update-heavy workload SA approaches the tier ratio — RocksDB's universal compaction is usually configured with a cap around 2×.

A B+ tree's excess is empty space in pages: splits leave two half-full pages, and a tree under random inserts settles near 70% fill, SA ≈ 1/0.7 ≈ 1.4. Under MVCC (UPDATE, DELETE and Dead Tuples) dead tuples add to that until VACUUM reclaims them — PostgreSQL bloat is space amplification with a local name. Sorted, compressed SSTable blocks typically shrink data 3–5×, which is why MyRocks stores the same dataset in a third of InnoDB's space; compression is the LSM's counterweight to its amplifications.

Amplification factors are constants of a design; what a workload pays is Σ (share of operation type × its amplification). At 90% point reads, a B+ tree's ≈ 1 page and an LSM's ≈ 1.06 blocks are equivalent and the B+ tree's page-granular writes are a rounding error. At 95% random-key ingest, the B+ tree pays a page write per few rows while the LSM pays a sequential append — a 10–20× difference in disk bandwidth. At 50% range scans the LSM's 7–36 runs per scan dominate everything else.

The interactive lets you move the mix and watch the ranking flip. That flip, not any single number, is the lesson: the question "which engine is faster?" has no answer until the workload is on the table, and the amplification triangle is how you reason about it before you have a benchmark.

Athanassoulis et al. (2016) named the triangle: Read overhead, Update overhead, Memory (space) overhead — an access method can minimise two of the three at the expense of the third, never all three. A B+ tree is read-optimal with update overhead; a log is update-optimal with read and space overhead; leveled LSMs trade towards read and space; tiered LSMs trade towards update. Every tuning knob — level ratio, bloom bits, compaction strategy, fill factor — is a slider along one edge of that triangle.

It also explains hybrids. Fractal trees and Bε-trees buffer updates inside B+ tree nodes to lower write amplification while keeping one sorted structure. WiredTiger offers both a B+ tree and an LSM layout in one engine. None escapes the triangle; each picks a point on it.