B-tree versus LSM tree: measured amplification and workload trade-offs

B-trees maintain a sorted page-oriented index and update pages in place under a recovery protocol. LSM trees buffer sorted updates in memory, flush immutable runs, and compact overlapping runs later. Neither family has one universal I/O count, latency, or amplification factor.

The useful comparison is workload-specific: point/range read mix, update skew, key/value sizes, cache hit rate, durability, compaction style, compression, device behavior, and tail latency under background work. Measure logical bytes, physical reads/writes, space, stalls, and recovery together.

Модель и предпосылки

• Teaching estimate height ≈ ceil(log_F(N)) assumes roughly uniform fanout F; real occupancy, root caching, page splits, and concurrency change I/O.
• Write amplification over an interval is physical bytes written / logical bytes ingested; it is a measurement with an explicitly named boundary.
• Leveled and tiered compaction trade read, write, and space amplification differently; compaction is incremental/background work but can cause stalls when debt grows.

Проверяемые утверждения

• C1. A B-tree height is logarithmic in entries under a fanout model, but physical I/O depends on cache, occupancy, page layout, and write/recovery behavior.
• C2. An LSM write enters a mutable memory structure and durable log before immutable sorted runs and later compaction.
• C3. Leveled compaction tends to trade higher write amplification for lower read/space amplification than tiered compaction.
• C4. RocksDB exposes measured compaction bytes, stalls, and write amplification; backlog can throttle or stop writes.
• C5. Bloom filters reduce unnecessary point-lookups in runs but do not make range scans free and can return false positives.

Исполняемые сценарии

B-tree update path. A logical update uses the durability log and cached pages; splits and physical writes are conditional, not fixed.

LSM write and flush. The foreground writes log plus memtable; immutable-run creation and compaction move work into background queues.

LSM point read. Memtable, run indexes, and Bloom filters reduce candidate work; a positive filter still needs authoritative lookup.

Compaction debt and write stall. Background compaction is incremental, but excessive debt can deliberately slow or stop writes.

Assumption-labelled math. Height and amplification formulas are useful only with units, boundaries, and measured inputs.

Ошибки проектирования

• Не пишите «B-tree insert = 2 I/O» или «LSM insert = 1 I/O»: WAL, cache, splits, flush, batching и compaction меняют путь.
• Не сравнивайте latency без steady-state compaction debt и tail percentiles.
• Не переносите недокументированные детали одного managed service на всё семейство LSM.
• Удаление в LSM создаёт tombstone; место и старые версии исчезают только по правилам compaction/snapshot retention.

Границы гарантии

• B-tree и LSM — семейства; PostgreSQL, InnoDB, RocksDB и Cassandra имеют разные concurrency/recovery/compaction реализации.
• Compression может уменьшить physical bytes и увеличить CPU; space amplification измеряется вместе с transient compaction headroom.
• Benchmark должен включать restart/recovery, потому что отключение WAL меняет durability, а не только throughput.

Связанные материалы

Официальные и первичные источники

1. PostgreSQL: B-Tree Indexes
2. RocksDB: Compaction
3. RocksDB: Compaction Stats and DB Status
4. RocksDB: Universal Compaction
5. O’Neil et al., The Log-Structured Merge-Tree