The log-structured merge tree exists because the B-tree has one genuine weakness, and the whole design follows from attacking that weakness directly and accepting the costs that follow.

The weakness being attacked

Inserting a key into a B-tree means placing it in sorted position inside a specific page, which is an arbitrary page somewhere in the structure. A stream of random keys is therefore a stream of random writes, and random writes are far more expensive than sequential ones on every storage device.

Naming the weakness precisely is what makes the alternative comprehensible. The problem is not that the B-tree is slow in general, it is that one specific requirement, keeping everything in sorted order at all times, forces a write pattern that storage devices handle badly. Relaxing that one requirement is the entire idea.

The relaxation

Do not keep everything sorted at all times. Keep recent writes in memory, and when enough accumulate, write them out as one sorted file in a single sequential pass. The structure is then a collection of sorted files rather than one sorted structure.

Every property of the design, good and bad, follows from this one change. Writes become sequential because a batch is written once in order. Reads become harder because a key could be in any of the files. And a background process becomes necessary because the number of files would otherwise grow without limit.

Why sequential writing is so much cheaper

On a rotating disk a sequential write avoids seeks entirely. On flash, a sequential write of a large block aligns with the device's erase unit, so the controller writes it once, whereas scattered small writes force read-modify-write cycles internally.

The ratio is large enough to justify a complete structural redesign, often between ten and a hundred times depending on the device and the write size. This is why the design is worth its complexity, and it is also why the advantage shrinks as devices get better at random writes, which is a real trend rather than a hypothetical one.

The memory component

Incoming writes go into an in-memory sorted structure, typically a skip list or a balanced tree, which is cheap to insert into and already in the right order when the time comes to write it out.

Two details about this component matter more than its choice of data structure. It must be ordered, so that the file it produces is sorted without a separate sort step, and it must support concurrent insertion well, since it absorbs the entire write load of the system. The ordering requirement is why a hash table is not an option here.

Durability before the flush

Data in the memory component would be lost on a crash, so each write is appended to a log on durable storage first. The log is written sequentially and is discarded once the corresponding memory component has been flushed.

The arrangement is worth noticing because it is the same write-ahead logging discipline a B-tree engine uses, applied to a different structure. It also means the design has two sequential write streams, the log and the flushed files, and that the log is the only thing standing between an acknowledged write and data loss.

Flushing and immutability

When the memory component reaches a size threshold it is written out as an immutable sorted file and a new empty memory component takes over. The file is never modified afterward.

Immutability is the property that makes everything else simple, and it is worth drawing out. A file that never changes needs no locking for readers, can be cached aggressively without invalidation, can be checksummed once, and can be replicated by copying bytes. A great deal of the design's operational simplicity comes from this one decision.

How a read works

Check the memory component, then each file from newest to oldest, stopping at the first occurrence of the key, because a newer occurrence supersedes an older one. A read may therefore touch many files.

This is the cost side of the trade stated plainly. Where a B-tree lookup is a bounded descent of three or four reads, a log-structured lookup may consult every file in the structure, and the number of files is a tuning decision. Everything in the next sections about compaction and filters exists to bound this cost.

Deletes as records rather than removals

A delete cannot remove a key from an immutable file, so it writes a marker saying the key is deleted. A read that finds the marker first reports the key as absent, and the marker is discarded only when no older occurrence can remain.

The consequence is that deleting data makes the structure larger until compaction catches up, which is counterintuitive and the source of real operational surprises. A workload that deletes heavily can be slower and larger after the deletions than before, which is the opposite of what an operator expects.

Updates as the same mechanism

An update is a new record for the same key, superseding the old one. There is no in-place modification anywhere in the design, which is where the name comes from and what makes every write sequential.

This uniformity is an underappreciated virtue. Insert, update and delete are the same operation on the write path, differing only in payload, so there is one code path, one cost model and one set of failure modes rather than three. The B-tree, by contrast, has meaningfully different costs for each.

The three costs this creates

Reads may touch many files. The same data is rewritten repeatedly by compaction, so more bytes are written to the device than the application wrote. And obsolete versions occupy space until compaction removes them.

These three are read amplification, write amplification and space amplification, and the central fact about the design is that they cannot be minimised simultaneously. Every compaction strategy is a choice about which to favour, which is why there are several strategies rather than one best one.

Why the design appeared when it did

The structure was described in the nineteen nineties and became dominant in the twenty tens, once datasets routinely exceeded memory and write rates routinely exceeded what random writes could sustain.

The timing is informative because it shows the design is a response to a ratio rather than to an abstract improvement. When data fitted in memory and write rates were modest, a B-tree's random writes were affordable and its simpler cost model was worth having. When ingestion rates rose faster than random write throughput did, the balance moved, and a structure that had existed for two decades without wide adoption became the obvious choice almost everywhere at once.

Why compression favours this design

Blocks written once and never modified can be compressed as large units with a general algorithm, whereas a page that must remain individually updatable can only be compressed in ways that survive in-place modification.

The practical gap is substantial, often two to four times against a B-tree's page-level compression, and it is easy to forget when comparing the two designs because it does not appear in any of the three amplifications. A store that writes ten times as many bytes as the application but compresses three times better is writing three and a third times as many bytes to the device, which is a materially different conclusion from the raw figure.

What to take from the trade

Three things. The design relaxes exactly one requirement, that data stays sorted at all times, and every other property follows from that single change. Sequential writing is ten to a hundred times cheaper than random writing, which is what justifies the complexity, and immutable files bring a great deal of operational simplicity as a side effect. And the costs are read amplification, write amplification and space amplification, which cannot all be minimised at once, so every strategy in this design space is a choice between them.