Cairn
data structures · node-linked trees · O(1) amortized write (sequential) · O(L log s) read before compaction

↩ back to Node-Linked Trees

LSM Tree

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.

Try it

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.

Memtable (RAM)
Loaded 3 flushed runs, with user:3 deleted in the newest one.

Core operations

Reference implementation

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.

Pitfalls

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.

Where it shows up

Complexity

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.