Storage engines: LSM-tree vs B-tree, simulated

The diagram. The B+tree on the left (on a phone: on top): its pages by level, root at the top, each page’s fill shaded, its keys written in when they fit (otherwise used/capacity), the leaf chain dashed. A dot on a page means it is in the buffer pool (orange: dirty, not yet on disk). Splits, borrows and merges flash on the pages involved. Above the tree: the WAL, the buffer pool and the disk counters. The LSM-tree on the right: the WAL, the memtable (its keys, sorted) and the immutable memtable being flushed, then one band per level (L0, L1, …; one band for size-tiered). Each SSTable is drawn over the key range it covers, so overlap is visible; one row per sorted run. Ticks on a file are its fence pointers (one per block), the dark part is the share of tombstones, stripes mean it is being compacted. Operations travel as labelled packets: a write goes to the WAL and memtable; a lookup visits the memtable and then each file it has to read (a ✕ marks a file whose Bloom filter said "not here", skipped without I/O); a B+tree operation walks from the root to a leaf. Flushes and compactions move blocks from their input files to the level they write. Tap a page, a file, a level, the memtable, the WAL or the buffer pool to inspect it and act on it (look up a key, delete a page’s keys, compact a file down, flush, checkpoint).

Counters, per engine: write amplification, reads per lookup that finds its key, per lookup of a missing key, and per range scan, space amplification, splits and merges, buffer-pool hit ratio, Bloom-filter negatives and false positives, compactions, tombstones and write stalls.

Amplification over the run: write, space and read amplification against the number of operations, for both engines.

Do something: send 1–1,000 inserts, updates, deletes, lookups (of existing or missing keys) or 20-key range scans, with random, ascending, descending or Zipf-skewed keys; flush the memtable, run a full compaction, toggle Bloom filters, checkpoint the B+tree, or empty both engines.

Event log: splits, merges, flushes, compactions, stalls and checkpoints.

Engine settings rebuild the engines (listed below).

B+tree: pages split as keys arrive — ascending keys leave half-full pages with 50/50 splits; the rightmost-split optimisation fills them; random keys settle near 69% (ln 2).

B+tree: deletes, borrowing and merging — under-full pages borrow from a sibling or merge, and the root collapses.

LSM: WAL, memtable and flush to L0 — the write path, overlapping L0 files and newest-first reads.

Leveled compaction: the cascade — L0 → L1 → L2 with targets T times apart, and what it costs in writes.

Size-tiered compaction and its space spike — Cassandra’s STCS buckets, overwrites piling up, and a major compaction that briefly needs the old and the new data on disk.

Tombstones: deletes are writes — deletes add data, scans wade through tombstones, compaction drops them at the bottom.

Bloom filters save lookups of missing keys — a block read per run without filters, almost none with them.

Range scans favour the B+tree — one descent and a leaf walk against a block from every run.

Update-heavy: write amplification compared — a page rewritten per update against append and compact, and what a buffer pool does to the B+tree.

Playground — both engines, empty.

B+tree (Comer 1979): leaves hold entries and are chained; inner pages hold separators. An insert into a full leaf splits it 50/50 (or, with the rightmost-split option, leaves an appended-to last leaf full, as PostgreSQL and InnoDB do for ascending keys) and pushes a separator up, splitting inner pages and growing a new root as needed. A delete that leaves a page under half full borrows from a sibling or merges with it; a root with one child is removed. Page size is derived: 64 bytes of header plus the entries. Every page access goes through an optional LRU buffer pool (write-back: dirty pages reach the disk at eviction or checkpoint); every change appends a WAL record, and with full-page writes the first change to a page after a checkpoint puts the whole page in the WAL, as PostgreSQL’s full_page_writes does.

LSM-tree (O’Neil et al. 1996): a write appends to the WAL and goes into the memtable; a full memtable becomes immutable and is flushed to L0 as an SSTable while a new one takes writes (if the previous flush has not finished, or L0 has reached its stop trigger, writes stall). Each SSTable has a Bloom filter with k = round(bits per key × ln 2) and fence pointers, one per block, both in memory: a point lookup asks each candidate file’s filter and reads one block on a "maybe"; a range scan reads the blocks covering the range in every overlapping file.

Leveled compaction (RocksDB): L0 files overlap; at l0Trigger files they are merged with the overlapping L1 files. Level 1’s target is l0Trigger × memtable entries and each level below is T times larger; a level over target merges one file (round-robin by key) with its overlap below. Files in L1+ never overlap. Size-tiered (Cassandra STCS): runs are bucketed by size (0.5–1.5× the bucket average, small ones together) and a bucket with min_threshold runs is merged, up to max_threshold. Lazy leveling (Dostoevsky): levels above the last accumulate up to T runs and merge them into the next level; the last level is a single run that incoming runs merge into.

Merging keeps the newest version of each key. A tombstone is dropped only when no file outside the merge at that level or below (for STCS: no other SSTable) covers its key.

Amplification: write = (WAL + page writes × page size) ÷ user bytes for the B+tree, (WAL
flushes + compactions) ÷ user bytes for the LSM-tree; read = disk page or block reads per operation; space = (pages × page size + WAL since checkpoint) or (SSTables + live WAL + a running compaction’s output) ÷ live bytes.