A B-tree commits to one idea: every key lives at a single, fixed spot on disk, and an update finds that spot and rewrites it in place. That's a great deal for reads — find the leaf, done — but it means every write is a disk access to wherever that leaf happens to live, essentially a random address relative to whatever was written just before it. A workload that's heavy on writes pays for that randomness on every single one.
A log-structured merge (LSM) tree refuses to ever write in place. New writes — including deletes — only ever land in an in-memory buffer, the memtable. Once that buffer fills up, its entire contents are sorted and written out in one sequential pass: a new, immutable sorted run (often called an SSTable, the name Google's Bigtable paper gave it), stacked above every older run. Nothing already on disk is ever touched again by a write. The cost moves instead to reads: a key that isn't in the newest run has to be chased backward through older ones until something matches, or every run comes up empty. Left unchecked, that cost only grows — a background process called compaction periodically merges old runs back down to keep it bounded.
Three rounds of writes are loaded below, flushed into three on-disk runs (memtable threshold: 3
writes per flush), with user:3 deleted in the most recent round. Look up
user:3 first — its tombstone in L0 shadows the older value sitting two runs
down, so it correctly reports "not found" after 2 stops. Now click Compact top run
only: a real compaction bug. Merging just L0 by itself finds no live value in
that run to pair the tombstone against, so it gets dropped as "resolved" — but L2, never
touched by this compaction, still holds the original value. Look up user:3 again and
watch it come back. Click Reset, then Compact all runs instead —
merging every run at once is the one scope where dropping that tombstone is actually safe, and the
key stays gone for good.
user:3 deleted in the newest one.O(1)
amortized; may trigger a flush.n newest runs into one, keeping only the
newest version of each key. Dropping a tombstone outright is only safe when the merge reaches
every run that could still hold the value it's shadowing — in practice, when n is
every run that currently exists.class LSMTree {
#memtable = new Map();
#levels = []; // levels[0] is newest
#seq = 0;
#threshold;
constructor(threshold) { this.#threshold = threshold; }
set(key, value) {
this.#memtable.set(key, { value, tombstone: false, seq: this.#seq++ });
if (this.#memtable.size >= this.#threshold) this.#flush();
}
del(key) {
this.#memtable.set(key, { value: undefined, tombstone: true, seq: this.#seq++ });
if (this.#memtable.size >= this.#threshold) this.#flush();
}
#flush() {
const sorted = [...this.#memtable.entries()].sort((a, b) => (a[0] < b[0] ? -1 : 1));
this.#levels.unshift({ entries: new Map(sorted) }); // one sequential write
this.#memtable = new Map();
}
get(key) {
if (this.#memtable.has(key)) return this.#resolve(this.#memtable.get(key));
for (const level of this.#levels) {
if (level.entries.has(key)) return this.#resolve(level.entries.get(key));
}
return undefined; // checked every run, genuinely absent
}
#resolve(e) { return e.tombstone ? undefined : e.value; }
// merges the `count` newest runs into one. Only pass dropTombstones=true
// when count === this.#levels.length — anything less and an un-merged
// older run might still be shadowed by the tombstone you're about to drop.
compact(count, dropTombstones) {
const merged = new Map();
for (let i = count - 1; i >= 0; i--) {
for (const [k, e] of this.#levels[i].entries) merged.set(k, e); // newer seq overwrites
}
if (dropTombstones) {
for (const [k, e] of merged) if (e.tombstone) merged.delete(k);
}
this.#levels.splice(0, count, { entries: merged });
}
}
Verified against a plain-Map ground-truth oracle (sequential overwrite semantics,
delete removes the key outright) across 20,000 randomized trials of 6–11 set/del/
compact operations each, over three possible keys. A compaction policy that always
drops any tombstone it finds, regardless of how many runs the merge actually covered, disagreed
with the oracle on at least one of the three keys in 1,854 of 20,000 trials (9.3%),
1,938 individual wrong answers total. A depth-aware policy — only drop a tombstone when
count equals the run count that exists at that moment — matched the oracle in all
20,000 trials, 0 wrong answers. This exact class is what the demo above runs.
A tombstone dropped by anything less than a full compaction can let a deleted key come
back. Minimal repro, run directly against the class above: set('a', 'v1'),
then del('a'), each flushed to its own run (L0: tombstone, L1:
v1). Calling compact(1, true) — merge only the top run, drop any tombstone
found — leaves L0 empty and L1's old value untouched underneath it.
get('a') now returns 'v1': a value that was explicitly deleted, back from
the dead, with no error anywhere. Calling compact(1, false) instead (keep the
tombstone on a partial merge) correctly returns undefined, and a later
compact(levelCount, true) — once that merge is actually full — drops the tombstone for
good with the same correct result. The fuzz numbers above quantify exactly how often skipping this
rule goes wrong in practice: not a rare edge case, close to 1 in 10 random short operation
sequences.
Read cost grows with every unmerged run, with no ceiling until compaction runs. Measured directly against the same class: inserting 2,000 unique keys with a memtable threshold of 50 produces 40 on-disk runs. Before any compaction, looking up a key that's actually present costs an average of 21.4 stops (memtable plus however many runs down it happens to sit, worst case 41) — and looking up a key that was never written costs the full 41 stops every single time, because confirming absence means checking every run. After one full compaction down to a single run, every lookup — present or absent — costs exactly 2 stops: roughly 10.7× fewer for a present-key lookup on average, 20.5× fewer for an absent-key or worst-case lookup. Compaction isn't housekeeping on the side here — it's the only thing standing between this structure and an unbounded read cost.
Time: a write costs O(1) amortized into the memtable, plus a
O(m log m) sort every m writes (one flush) — amortized
O(log m) per key — and critically, the disk access itself is one sequential write
regardless of how scattered the keys were, not a seek to a key-dependent address the way a
B-tree's in-place update is. (That seek-vs-sequential gap is the textbook, structural reason this
trade exists — real spinning disks and flash write amplification both make it concrete, but it's
not a number this VM's own SSD can measure honestly, so it's stated as the standard architectural
reason rather than invented here.) A read with L unmerged runs on disk, each resolved
by binary search in O(log s) for a run of size s, costs
O(L log s) worst case — and grows without bound as flushes accumulate, exactly the
first Pitfall measured above. Keeping compaction running so L stays near
O(log n) brings reads back down to roughly O(log n log s), the same
asymptotic shape as a B-tree's O(log_t n) — the entire reason compaction has to run
continuously, not as a one-off cleanup.
Space: O(n) once fully compacted, but a superseded value or an
unresolved tombstone counts as live bytes on disk until a compaction actually reaches it — a real,
temporary overhead this page doesn't separately measure beyond the two Pitfalls above.