LSM Trees
The write-optimised alternative: memtables, SSTables, bloom filters, compaction, the three amplifications — and an honest B+ tree vs LSM comparison.
When a database must absorb far more writes than it serves reads, updating a B+ tree page per row is the wrong shape. The log-structured merge tree appends every write, sorts in memory, flushes immutable sorted files and reconciles them later — trading cheap writes for a read path that has to look in several places.
A memtable flush has to become a file that a reader can search without loading it, that compresses well, and that many readers can share without locks. The SSTable answers with sorted data blocks, a sparse index with one entry per block, a bloom filter and a footer that says where everything is — and it never changes after it is written.
A point read in an LSM tree may have to consult ten files, and most of them do not hold the key. A bloom filter answers "definitely not here" from a few bits per key, with no false negatives and a tunable false-positive rate — turning ten block reads into one.
Every flush adds a file; every update adds a version; every delete adds a tombstone. Compaction is the background k-way merge that folds files together, keeps the newest version of each key, drops the rest — and, depending on how files are chosen, decides whether the engine is cheap to write, cheap to read, or cheap on disk.
Every storage engine pays for a logical operation with more physical work than the operation itself: extra bytes written, extra pages read, extra bytes stored. Naming the three amplifications precisely — and seeing that no design minimises all of them — is the vocabulary for comparing B+ trees, leveled LSMs and tiered LSMs honestly.
Two ways to organise bytes on disk: keep one sorted structure and update it in place, or append sorted runs and merge them later. Neither is better. Each is the right answer to a different workload, and the comparison is a table of dimensions, not a verdict.