Write new values now, merge them later

A B+ tree maintains an ordered structure as entries change. Another approach accepts new versions into memory and later writes them as sorted files. This is the idea behind a log-structured merge tree, usually shortened to LSM tree.

We will focus on how a read finds the newest value when older copies remain. Assume one writer, no historical readers, and completed file publications. Crash-safe publication is a separate responsibility developed in the recovery stage.

Keep the old file and add a new one

Yesterday’s sorted file contains product 27 at price 20. Today the seller changes it to 25. Instead of modifying yesterday’s file in place, the engine places the new value in an ordered memory structure, often called a memtable. When that structure fills, it becomes another sorted file.

Older file
12 → 8
27 → 20
46 → 35

Newer file
27 → 25
51 → 12

Product 27 appears in both files. A lookup must prefer its newer version rather than return whichever copy it happens to encounter first.

The engine records enough ordering information to distinguish versions. For a read of current data, it chooses the newest eligible value across memory and relevant files. Our two-file model makes “newer file wins” sufficient; real layouts need explicit sequence and visibility rules.

Why merging is part of the design

As files accumulate, reads may need to inspect more places. Compaction merges sorted data into a new representation, combining versions and removing obsolete entries when safe. In our example, a completed merge can retain 27 → 25 and discard 27 → 20 because no reader needs the earlier value.

Compaction reads and writes bytes. Accepting writes quickly does not remove that later work. If writes create merge work faster than the storage system can process it, files and maintenance backlog accumulate. Eventually the engine must slow or stop admission to catch up.

A recoverable log is commonly used before acknowledging memory-only updates. The sorted files and the log serve different jobs: one organizes lookup data; the other helps recover accepted changes. Their exact ordering and acknowledgement rules depend on the engine.

Deleting is also a version

Suppose a newer update deletes product 27. Simply removing it from memory would expose the older file’s price of 20 again. A tombstone is a recorded deletion that tells a read to stop and report absence.

When may compaction discard that marker?

Look for an older value that could reappear

Only when it is safe with respect to every older source and retention requirement that could still expose the key. In our simplified case, remove the marker together with all older copies it suppresses. If the file containing 27 → 20 remains searchable, dropping only the marker resurrects deleted data.

LSM storage moves part of update maintenance into later merging. The choice is about when work happens and which read/write costs the workload can tolerate.

RocksDB’s overview describes a real LSM storage engine. Our trace isolates version precedence rather than prescribing all its file-level rules.

Extended reference

The extended chapter preserves the original technical coverage, additional examples, and citations. The explanation above supplies the concepts needed for this page; the reference develops the specialist cases.

Find a section from the original chapter