The Log Structured Merge Tree

9 min read

If you're wondering what led to the writing of this paper, read up on WALs.

How LSM Trees Work

The Core Idea

At a high level, the Log-Structured Merge-tree (LSM-tree) solves database write bottlenecks by turning slow, random disk updates into fast memory writes and continuous sequential disk flushes.

Traditional database indexes (like B-trees) attempt to update records directly in place on disk, forcing the drive heads to perform random seeks for almost every write. An LSM-tree avoids this bottleneck entirely through a simple three-step strategy:

1. Write everything to RAM first: Incoming inserts, updates, and deletes are saved immediately into a fast, memory-resident tree structure with zero disk I/O cost.
2. Batch changes in memory: Instead of updating disk files record-by-record, the system lets writes accumulate in memory until a threshold size is reached.
3. Flush and merge sequentially: When memory fills up, the system reads sorted data from disk in large contiguous chunks, merges it with the accumulated memory data, and writes the sorted result back out to new locations on disk as a continuous stream.

By deferring updates and writing data in large multi-page blocks, the system converts small, random disk accesses into high-speed sequential writes — bypassing the physical seek times and rotational delays of hard drive arms.

From Memory Tree to Disk Blocks

In Memory: The $C_0$ Tree

Incoming writes (inserts, updates, and deletes) land directly in an in-memory balanced search tree — an AVL tree or 2-3 tree — called the $C_0$ component. Because $C_0$ lives entirely in RAM, node sizes don't need to match disk page sizes; nodes grow and rebalance at electronic speeds with zero disk I/O cost. New entries are simply added to the tree — nothing is ever updated in place on disk.

Watch five fresh writes build the tree in memory — (15, "Alice"), (07, "Bob"), (22, "Carol"), (04, "Dave"), (10, "Eve"):

Step 1: (15, Alice) arrives — becomes the root
 
              [15: Alice]
 
Step 2: (07, Bob) and (22, Carol) arrive
 
              [15: Alice]
              /         \
       [07: Bob]     [22: Carol]
 
Step 3: (04, Dave) and (10, Eve) arrive —
        tree rebalances to keep O(log N) depth
 
              [15: Alice]
              /         \
       [07: Bob]     [22: Carol]
       /      \
 [04: Dave] [10: Eve]

Flushing: Serialize and Write Sequentially

As writes keep arriving, $C_0$ eventually reaches its size threshold. At that point the tree is serialized into flat, page-structured disk blocks:

1. In-order traversal. The engine walks the tree in-order, extracting every entry in strictly sorted key order:

walk → (04, Dave) (07, Bob) (10, Eve)
       (15, Alice) (22, Carol)

2. Pack pages into the filling block. Entries are packed tightly into page-sized leaf nodes inside a RAM buffer called the filling block:

FILLING BLOCK (RAM buffer)
+---------------------------+
| Page 1: (04,Dave)(07,Bob) |
| Page 2: (10,Eve)(15,Alice)|
| Page 3: (22,Carol) ...    |
+---------------------------+

3. One continuous disk write. The full filling block is streamed to a free contiguous area on disk in a single sequential write — no arm seeks, no rotational waits — forming the leaf level of the disk-resident $C_1$ component:

C1 on disk:  [ Page 1 | Page 2 | Page 3 ]
             (written at address X)

An upper-level directory structure for $C_1$, held in its own memory buffer, maps key ranges to the new disk block.

The Rolling Merge: Continuous Background Merges

After the flush, $C_0$ starts fresh and keeps accepting writes. When it fills up again, the engine doesn't just write a second independent block — it merges the new entries into the existing disk data through an ongoing rolling merge (the same merge idea behind SSTable compaction):

C0 tree (new)           C1 block 1 (old, on disk)
(02,Frank) (12,Grace)  (04,Dave)(07,Bob)(10,Eve)
         \                   /
          v sequential read v
     +--- EMPTYING BLOCK (RAM) ---+
     |  old C1 pages being merged |
     +----------------------------+
                |
          2-way merge sort
                |
                v
     +--- FILLING BLOCK (RAM) ----+
     | (02,Frank)(04,Dave)(07,Bob)|
     | (10,Eve)(12,Grace)(15,Alice)|
     +----------------------------+
                |
      one sequential write
                v
C1 on disk:  Block 2 (NEW): [ P1 | P2 ]  (address Y)
            Block 1 (OLD): [ INVALIDATED ]

The merge proceeds as a continuous cycle:

1. Emptying block read: the merge cursor reads contiguous $C_1$ leaf pages from disk into an emptying block buffer in RAM.
2. Two-way merge: sorted $C_0$ entries and emptying block entries are merge-sorted together.
3. Filling block assembly: the merged, sorted result is packed tightly into a new filling block.
4. Out-of-place sequential flush: the filling block is written to a brand-new disk location as one contiguous multi-page unit.
5. Invalidation: the old $C_1$ block is invalidated and marked for space recovery — no in-place cleanup required.

This cycle never stops: memory batches writes, background merges continuously fold them into disk, and every physical write stays sequential. The random updates users see at the logical level have been completely transformed into sequential disk streams at the physical level.

Updates and Deletes

In an LSM-tree, updates and deletes never modify existing disk pages in place. Instead, they are treated as append-only operations. To reconcile these append-only changes — both in the Write-Ahead Log (WAL) and across the in-memory and disk components — the LSM-tree uses tombstones, shadowing, and annihilation during the rolling merge process.

We'll continue with our running catalog from the previous section: after the rolling merge, the disk block ($C_1$) holds (02, Frank) (04, Dave) (07, Bob) (10, Eve) (12, Grace) (15, Alice), and $C_0$ has been cleared and is accepting fresh writes.

The Role of the Write-Ahead Log (WAL)

Before any write lands in the in-memory tree ($C_0$), it is appended to a sequential Write-Ahead Log (WAL) on disk.

• Purpose: The WAL guarantees durability. Because it is purely append-only, writing to it requires minimal disk head movement.
• No search function: The WAL is not an index; it exists solely for crash recovery.
• Crash recovery: If the system crashes, the engine replays the log from the last recorded checkpoint to reconstruct $C_0$ exactly as it was — including all recent updates and deletes.

How Deletes Work: Tombstones & Annihilation

Searching disk to erase a deleted record immediately would require slow, random disk reads. Instead, the LSM-tree defers the deletion:

1. Insert a tombstone: a special delete marker is inserted into $C_0$, tagged with the target key.
2. Filter reads: when a query looks up that key, it checks $C_0$ first. Encountering the tombstone tells the query immediately that the key was deleted — no need to check older disk components at all.
3. Annihilate during the rolling merge: as the tombstone migrates outward to disk components ($C_1, C_2, \dots$) during the rolling merge, it eventually meets the old disk entry for that key. The merge annihilates both at once — neither the old entry nor the tombstone appears in the newly written disk block.

In our catalog, delete(15) removes Alice. The tombstone lands in $C_0$ as an ordinary insert — nothing on disk is touched:

C0 tree after delete(15):
 
        [15: TOMBSTONE]

While the tombstone sits in memory, read(15) resolves instantly: it hits the marker in $C_0$ and returns "deleted" without ever touching the disk block. When $C_0$ fills up, the next rolling merge finishes the job:

C0 (memory)          C1 old disk block
(15, TOMBSTONE)     (02,Frank)(04,Dave)(07,Bob)
                     (10,Eve)(12,Grace)(15,Alice)
        \                   /
         ------ merge ------
                        |
         one sequential write
                        v
new C1 block:
(02,Frank)(04,Dave)(07,Bob)
(10,Eve)(12,Grace)

Key 15 is gone entirely: the tombstone and the old (15, Alice) annihilated each other, and neither was written to the new block.

How Updates Work: Shadowing & Replacement

Updates are handled as a delete followed by an insert, resolved lazily the same way:

1. Shadow in memory: the new value is inserted into $C_0$ under the existing key.
2. Match early in searches: read queries traverse components from newest to oldest. Since the updated entry lives in $C_0$, the search finds the new value immediately and returns — the stale record still sitting on disk is shadowed.
3. Replace during the rolling merge: when the new entry is merged into a disk component that contains the old entry, the merge logic compares timestamps or sequence numbers. The newer entry wins, the older one is dropped from the new block, and the old block is invalidated.

In our catalog, update(07, "Bobby") corrects Bob's record. The new value lands in $C_0$ as an ordinary insert:

C0 tree after update(07, "Bobby"):
 
        [07: Bobby]

read(07) now finds (07, "Bobby") in $C_0$ first and returns the new value — the stale (07, Bob) still sitting on disk is shadowed. When the rolling merge runs, the newer entry simply wins:

C0 (memory)         C1 old disk block
(07, Bobby)         (02,Frank)(04,Dave)(07,Bob)
                     (10,Eve)(12,Grace)(15,Alice)
        \                   /
         ------ merge ------
                        |
         one sequential write
                        v
new C1 block:
(02,Frank)(04,Dave)(07,Bobby)
(10,Eve)(12,Grace)(15,Alice)

The merge compares sequence numbers, (07, "Bobby") replaces (07, Bob) in the new block, and the old block is invalidated. Both the delete and the update resolved lazily inside the same rolling merge — and not a single random disk write occurred anywhere.

Summary Matrix

Conclusion

The LSM-tree is really one idea carried to its logical end: since storage hardware is dramatically faster at sequential I/O than random I/O, design the entire storage engine so that it only ever does sequential I/O. Writes land in a memory tree, get batched, and stream out as sorted multi-page blocks; background rolling merges continuously fold them into disk; and even updates and deletes — the operations that would seem to demand in-place modification — are handled as appends, resolved later by shadowing and annihilation inside the merge.

Everything we covered — the $C_0$/$C_1$ components, the filling and emptying blocks, the rolling merge, tombstones — comes from the original 1996 paper by Patrick O'Neil, Edward Cheng, Dieter Gawlick, and Esther O'Neil: The Log-Structured Merge-Tree (LSM-Tree). It's remarkably readable, and it's the direct ancestor of the storage engines inside RocksDB, Cassandra, LevelDB, and most modern databases.

Related reads

• SSTables: The Sorted String Table — the immutable sorted files the rolling merge produces
• How WALs became a thing — the durability log and the HDD physics behind all of this
• DRAM — the tier the $C_0$ tree lives in