Piece 035 mentioned, in passing, that storage engines built on log-structured merge trees keep a Bloom filter per on-disk table so a read for a missing key can be ruled out without a disk seek. That sentence assumed a fair amount it never explained: what a log-structured merge tree actually is, what it's an alternative to, and why an engine built that way would need the trick at all. The alternative is the B-tree, which has been the default answer to "how do I index this on disk" since the 1970s, and the two designs make close to opposite bets about which cost — writing or reading — is more worth optimizing away.
A B-tree keeps data sorted in a tree of fixed-size pages, wide enough at each level (a high fan-out, often hundreds of keys per page) that even a huge dataset stays only three or four levels deep. A lookup walks down from the root, one page per level, doing a handful of comparisons per page, until it lands on the page holding the key — a small, bounded number of disk reads no matter how large the table gets, which is exactly what makes B-trees good at point lookups and range scans. A write is where the cost shows up: inserting or updating a key means finding its page and modifying it in place, and if that page has grown too full, the tree has to split it into two and update the parent page to point at both, which can cascade upward more than one level. Every one of these writes touches a page somewhere in the middle of a large file on disk, at essentially random locations relative to whichever page was written right before it — random writes, not sequential ones, and on spinning disks especially, random I/O is the expensive kind. Solid-state drives narrow that gap but don't erase it; write amplification from small random writes is still a real cost, just a smaller one.
A log-structured merge tree makes the opposite trade on purpose. New writes never modify anything in place; they go first into an in-memory sorted structure (the memtable) backed by a write-ahead log for durability — the same append-only-log move covered in 017, here used to protect the memtable rather than a whole database. When the memtable fills up, it's flushed to disk as a new, immutable, sorted file — an SSTable — and a fresh, empty memtable takes over. Nothing already on disk is ever edited; a later write of the same key doesn't overwrite the old value, it just becomes a newer SSTable that logically shadows the older one. This means every write, whether it's a fresh key or a thousandth overwrite of an existing one, costs exactly the same thing — a sequential append, first to the log, then eventually to a new sorted file — never a random seek into the middle of an existing structure. That's the entire appeal: write latency stops depending on how big the dataset already is or where in it a given key happens to fall.
The cost lands on the read side instead, and it lands in two places. First, because a key's most recent value could be sitting in the memtable, or in any of the SSTables flushed since it was last written, a lookup that doesn't already know which file has it may have to check several — the memtable, plus however many on-disk tables haven't yet been merged away. This is exactly the gap the Bloom filter in 035 fills: each SSTable carries one, so a query for a key that isn't in a given table can usually skip that table's disk seek entirely on the strength of a fast in-memory "definitely not," and only pays for a real seek on tables where the filter says "maybe." Second, the growing pile of SSTables has to be periodically merged — compaction — both to bound how many files a read might need to check and to actually reclaim space from keys that have been overwritten or deleted and are just taking up disk in an old, now-shadowed table. Compaction reads several sorted files, merges them into fewer, larger sorted files, and discards the superseded data — which means data written once gets read and rewritten again, sometimes several times over its life, entirely in the background, off the path of any individual write or read a client is waiting on. This is write amplification of a different kind than a B-tree's: not extra random I/O on the write's own critical path, but extra total I/O paid later, asynchronously, in exchange for having kept every actual write cheap and sequential when it happened.
Neither design is a strict improvement on the other; they're priced for different workloads. A B-tree is the right choice when point lookups and range scans need to be fast and predictable and writes are a smaller fraction of the load — which describes most traditional relational databases (PostgreSQL's and MySQL's default storage engines are both B-tree variants) and most filesystems. A log-structured merge tree is the right choice when write throughput is the bottleneck and reads can tolerate checking a few files and leaning on a Bloom filter to make that cheap — which describes Cassandra, RocksDB, LevelDB, and most engines built for high-ingest workloads like time-series data or logging, where the write volume genuinely dwarfs the read volume across the system's life.
This repository's own object store — git's — sits closer to the LSM
side of that line than the B-tree side, though the resemblance is
partial and worth being precise about rather than overstating. A new
git object is written as a loose file, immutable, named by its own
content hash (020), never modified once written — an append, not an
in-place update, exactly LSM's core move. Periodically, git
gc repacks the accumulated loose objects into a single packfile,
discarding objects that are no longer reachable — structurally the same
shape as compaction: many small immutable pieces merged into fewer,
larger ones, done as background maintenance rather than on the critical
path of any individual commit. Where the resemblance stops is the read
side: git doesn't maintain per-pack Bloom filters or a multi-level
hierarchy of sorted files that a lookup has to search across in the way
an LSM read does; a git object lookup mostly just checks the loose
objects, then the (typically singular, post-gc) packfile's own index.
It borrows LSM's write-side trick — never rewrite, append and compact
later — without needing LSM's read-side machinery, because a git
repository's read pattern and file count never approach the scale that
machinery exists to serve.