---
title: "LSM Tree"
description: "See fast writes defer sorting and merging while sequence rules keep overlapping versions correct."
source: https://vizlearn.app/cs/databases/lsm-tree
access: premium (interactive player requires Lifetime; this doc is free)
---

# LSM Tree

An LSM tree makes foreground writes fast by postponing where each update belongs on disk. It records a mutation durably, keeps the newest version in memory, then sorts and merges batches into immutable files. The bill arrives later: reads may search overlapping files, and background compaction rewrites records that are already stored.

Think of the write path as an inbox for changes. A write lands in the WAL and memtable without reorganizing its final disk neighborhood; flush and compaction sort the inbox in batches. The governing trade is simple: append now, organize later. Sequence numbers and newest-first reads keep that delayed organization correct.

## The Write Path: WAL, Memtable, and Flush

Every `put` and `delete` receives a monotonically increasing sequence number. The operation appends its record to the WAL before changing the memtable. In this lesson, that append is synchronously durable, so the write can be acknowledged after the WAL and memory update even when no SSTable has changed yet.

The memtable holds at most one current record per key. Writing key 20 twice replaces the older in-memory slot rather than consuming two distinct-key positions, although both mutations remain in the WAL until that log segment can be retired. A delete uses the same path with a tombstone value. It does not search old files and erase their copies in place.

When the number of distinct memtable keys reaches the configured capacity, the complete generation rotates into an immutable memtable. A fresh active memtable and WAL open immediately. The immutable entries then flush in ascending key order, regardless of their arrival order. Only after the new L0 SSTable is installed can the sealed WAL segment retire.

## LSM Tree Lifecycle: Step by Step

The default run uses a three-key memtable, compacts when L0 reaches two files, and performs:

`put 20 A, put 10 B, put 30 C, put 20 A2, get 20, delete 10, get 10, put 40 D, get 20`

1. **Write `20:A #1`, `10:B #2`, and `30:C #3`.** Each mutation follows WAL then memtable. The third distinct key freezes the first generation. Although keys arrived as 20, 10, 30, the flush writes `S1 = [10:B #2, 20:A #1, 30:C #3]`.
2. **Overwrite key 20 with `A2 #4`.** The newer version is in the active memtable while `S1` still physically contains `20:A #1`.
3. **Read key 20.** The read checks memory first and returns `A2 #4`. It does not continue into L0, where it would find stale `A #1`.
4. **Delete key 10 with tombstone `#5`.** The old `10:B #2` stays immutable in `S1`; the tombstone is the newer visible version.
5. **Read key 10.** The memtable tombstone stops the lookup. Treating it as a miss and continuing into `S1` would resurrect `B`.
6. **Write `40:D #6`.** The second generation reaches capacity and flushes as `S2 = [10:DEL #5, 20:A2 #4, 40:D #6]`. L0 now has two overlapping files, so compaction begins.
7. **Compact `S1` and `S2`.** For each key, the merge selects the record with the greatest sequence number. Key 20 keeps `A2 #4` and discards `A #1`. Key 10 selects tombstone `#5`; because this full merge includes every lower overlapping version and writes into the modeled bottommost level, both the tombstone and `B #2` can disappear. Keys 30 and 40 remain live.
8. **Install the new L1 run.** The serving result is `[20:A2 #4, 30:C #3, 40:D #6]`. Old L0 inputs retire only after this atomic serving-state change.
9. **Read key 20 again.** Memory and L0 are empty, so L1 returns `A2 #4`.

The closing evidence is exact: six logical mutations produce two sorted flushes; compaction reads six stored versions and writes three live L1 records.

## Read and Write Amplification

An LSM tree moves work; it does not erase it.

- **Write path:** WAL append and memtable update are foreground work. Sorted flush and compaction are deferred.
- **Read amplification:** without a Bloom filter, cache, or per-file index in the model, an L0 miss probes every overlapping run before reaching L1.
- **Write amplification:** compaction rereads and rewrites stored records. In the default trace, six input versions become three live output records.
- **Space amplification:** old values and tombstones coexist with their replacements until compaction proves they are obsolete.

Thresholds decide when you pay. A larger memtable usually produces fewer, larger flushes. Raising the L0 trigger lets more overlapping files accumulate, which delays compaction but lengthens an unfiltered miss. Lowering it spends background I/O sooner and keeps the read path shorter. The canvas counts records and sources rather than bytes or elapsed time, so it teaches the direction of each trade rather than a production tuning formula.

## When the LSM Tree Trade Is Worth It

LSM trees are a strong fit when writes dominate, storage can absorb sequential batch output, and the system has CPU and I/O budget for background compaction. Point reads need help: Bloom filters reject keys that cannot be in a file, sparse indexes locate candidate blocks, and a block cache avoids repeated device reads. Those mechanisms do not remove read amplification, but they reduce its physical cost.

For a read-sensitive workload, start compaction with fewer overlapping L0 files instead of letting the run count grow. The opposite choice defers background work but makes misses inspect more sources. In a production engine, an unchecked L0 backlog can also produce heavier compaction pressure or write stalls; this two-level canvas does not simulate either one.

Prefer a B+ tree when point and range reads dominate, ordered page locality matters, and in-place page maintenance is a better trade than an LSM's background rewriting. Prefer an LSM when absorbing sustained writes in append-and-batch form matters more than keeping every read path short by construction.

## Newest-First Reads

The modeled lookup order is:

1. active memtable;
2. L0 SSTables from newest to oldest; and
3. the single bottommost L1 run.

The first record found—live value or tombstone—terminates the search. Source order and record sequence solve related but different problems. Newest-first source order prevents an old file from masking a recent memory or L0 update. During compaction, selecting the greatest sequence number handles several versions of one key presented by different inputs.

L0 files may have overlapping key ranges, so a missing lookup can touch every one. Try **Read amplification**: three L0 runs remain below a trigger of four, then `get(99)` checks the memtable and all three files. The canvas reports four logical source probes. It does not claim four disk I/Os; caches, filters, and block indexes are deliberately outside this model.

## Compaction and Tombstones

Compaction is a sorted multiway merge. The current head of every selected run exposes its smallest unconsumed key. The merge chooses the minimum user key, gathers all current versions for that key, then selects the greatest sequence number. A live winner appends to the new sorted output. Losing versions are obsolete.

A tombstone winner needs an extra safety condition. Dropping it too early can reveal an older live record in an unselected lower file. This lesson may drop the tombstone only because compaction includes every L0 input and the complete overlapping L1 run, the destination is bottommost, and snapshots do not exist. Outside those boundaries, the tombstone must survive until no hidden older version can reappear.

Try **Tombstone safety** for the unsafe boundary. The trace leaves `10:B #1` in L1 and places `10:DEL #5` in a newer L0 run. The read stops at the tombstone. If that marker vanished before a compaction also consumed the older L1 record, `B` would become visible again.

The new L1 output does not serve partial results. It becomes visible in one install step; only then do the old inputs become obsolete and retire. That ordering is what keeps readers from observing a half-built level.

## LSM Tree Complexity

Let `M` be active memtable size, `F0` the number of overlapping L0 files, `S` records per L0 file, `L1` records in the bottommost run, `N` total compaction input records, and `k` selected runs.

| Operation | Growth in this model | Why |
| --- | --- | --- |
| Foreground mutation | `O(log M)` plus WAL append | update an ordered memtable after recording intent |
| Point lookup | `O(log M + F0 log S + log L1)` | check memory, every relevant L0 file newest-first, then L1 |
| Memtable flush | `O(M)` output | ordered memory already provides sorted-key iteration |
| Conventional k-way compaction | `O(N log k)` | a heap can choose the next run head |
| Displayed teaching merge | `O(Nk)` | the compact Python scans at most five visible heads for readability |

These expressions describe access growth. They are not latency promises: a WAL append may involve synchronization, an SSTable lookup may hit memory, and production engines use blocks, filters, caches, compression, and parallel background work.

## LSM Tree Edge Cases

- **Empty tree lookup:** only the memtable source exists, so a missing key stops after one logical probe.
- **Overwrite inside one memtable:** the key slot count stays unchanged while its sequence and value advance.
- **Exact-capacity rotation:** reaching—not exceeding—the configured distinct-key capacity freezes the generation.
- **Delete of an absent key:** the tombstone is still a sequence-bearing mutation. If an older run contains that key, the tombstone suppresses it; if no older version exists, scoped bottommost compaction may eventually remove the marker.
- **Newest L0 hit:** lookup stops at the first matching new run; older overlapping copies remain unconsulted.
- **Tombstone hit:** deletion is a terminal visible result, not permission to fall through.
- **Missing key across several runs:** every existing source appears in the read ledger, making read amplification inspectable.
- **Visualization limit:** the canvas represents at most 12 current user keys and 20 operations. Those are drawing limits, not LSM capacity or write-stall thresholds.

## Common Mistakes

- **Searching L0 oldest-first.** An immutable stale value can mask a more recent update.
- **Treating a tombstone as absence.** The lookup then falls through and resurrects a deleted value.
- **Picking the first compaction candidate.** Input order is not version order; the greatest sequence wins.
- **Dropping every tombstone during every compaction.** It is safe only when no unselected older overlap or snapshot can still need it.
- **Retiring inputs before installing output.** Readers can observe a gap or a partial result.
- **Calling an SSTable rewrite part of the acknowledged foreground write.** The default trace acknowledges the WAL and memtable state before flush.
- **Reading source probes as physical I/O.** Filters, indexes, caches, and block placement decide actual device work.

## A Note on Simplification

This is a serialized, two-level teaching model with a synchronous durable-WAL assumption, one active and at most one immutable memtable, overlapping L0 files, one complete L1 run, and full-range compaction into bottommost L1. It omits snapshots, Bloom filters, sparse and block indexes, block cache, compression, checksums, manifests and version sets, recovery replay, concurrent writers, multiple background jobs, partial overlap picking, output-file sizing, and write stalls. Real LevelDB- and RocksDB-style engines make those policies more granular. Tombstone removal is safe here only under the full-overlap, bottommost, no-snapshot scope shown by the trace.