Part 1 · A single truthful copy

Storage Engines I: Logs, Hash Indexes, and B-Trees

Lesson 02 showed that the access pattern is part of the contract — that at scale you sometimes store the data already shaped for the query, with the key design standing in for the plan. But that begged a question it deferred: what makes a lookup or a scan actually cheap on the disk underneath? Once you have bytes you trust, you have to put them somewhere — and survive the machine losing power mid-write, and find one record again among a billion. This lesson opens the storage engine: the layer that turns a write into something durable and a read into something fast. We build it from the cheapest durable primitive there is — an append-only log — and stop at the B-tree, the index that powers almost every relational database you have used.

Book source

Original synthesis inspired by Martin Kleppmann, Designing Data-Intensive Applications, Chapter 3 (Storage and Retrieval) — the log-structured arc, the Bitcask hash index, the write-ahead log, and B-tree page mechanics. Prose and examples here are our own.

Linear position

Prerequisite: Lesson 02 (query languages and access-pattern design) — you know the access pattern is part of the contract, and you carry the workload vocabulary (point read, range scan, write throughput, tail latency) we use to judge each design.
New capability: You can reason from first principles about why a write is cheap or expensive, design a point-lookup index and know when it falls over, explain why every serious database keeps a write-ahead log, and estimate how many disk pages a B-tree lookup and a B-tree write actually touch.

The plan

Five moves. (1) Build the simplest durable database — an append-only log — and see why sequential append is the cheapest durable write and how a crash is just a replay. (2) Notice reads are now hopeless without an index; build a Bitcask-style hash index for point lookups and find its two hard limits. (3) Introduce compaction to keep the log from growing forever. (4) Generalize the log into the write-ahead log (WAL) — the single ordered-durable-changes abstraction this whole track reuses as replication stream, CDC source, and audit trail. (5) Build the B-tree, walk a root-to-leaf lookup with real numbers, and price its defining cost: write amplification. A trade-off table closes the loop.

1 · The cheapest durable database: an append-only log

Strip a database down to its job: remember a write even if the power dies one millisecond later. The smallest thing that does this is a file you only ever append to. To store set(k, v), you write one record — the key, the value, maybe a timestamp — onto the end of the file and call fsync so the operating system actually flushes it to the physical disk. That's the whole write path.

log file (grows to the right, never overwritten) +--------------+--------------+--------------+--------------+ | set u1 = "A" | set u2 = "B" | set u1 = "C" | set u2 = "D" | +--------------+--------------+--------------+--------------+ offset 0 offset 14 offset 28 offset 42 <- append here next ^ ^ latest value of u1 latest value of u2

Why is this the cheapest durable write? Because it is sequential. On a spinning disk the head never seeks — it writes a continuous track. On an SSD, large sequential writes align with the flash erase-block structure and avoid the read-modify-write churn that random writes cause. Either way, sequential I/O is often one to two orders of magnitude faster than scattered random I/O, and an append is the most sequential write pattern that exists: you always write to exactly one place, the end.

Durability and recovery come almost for free. The log is the record of what happened, in the order it happened. After a crash you don't reconstruct state by guessing — you replay: read the file front to back, applying each record, and you arrive at the last consistent state the disk actually persisted. A half-written final record (torn by the crash) is detected by a length or checksum field and discarded. This idea — that an ordered, durable log is the source of truth and current state is a derived replay of it — is the spine of the entire track. Hold onto it.

Worked number — why sequential wins

A commodity NVMe SSD might sustain ~3,000 MB/s of sequential writes but only ~400 MB/s equivalent throughput on tiny random 4 KB writes once you account for write-amplification inside the drive. For a stream of 200-byte records, appending sequentially can absorb on the order of 10,000,000+ records/s of raw bandwidth; scattering those same records to random offsets across a large file can drop you below 1,000,000/s. Same data, same drive — the access pattern alone is a 10× difference. That is why nearly every high-throughput store, from Kafka to LSM engines (lesson 04), is built on an append.

2 · Reads break — so we add an index

The append-only log is a fantastic writer and a terrible reader. To answer get(u1) you must scan the whole file looking for the last record with key u1 (the newest value wins — earlier ones are stale history). With a billion records that is a billion-record scan per lookup. Unusable.

The fix is an index: a separate data structure, derived from the log, that maps a key to where its current value lives so you can jump straight to it instead of scanning. An index is pure read-side machinery — it adds no information, it just makes lookups fast. And here is the first universal law of storage engines: every index you add speeds reads and slows writes, because every write must now also update the index. There is no free index.

The simplest useful index is a hash index, the design behind Bitcask (Riak's default engine). Keep an in-memory hash map: key → byte offset of its latest record in the log. Writes still append to the log and update the one map entry. Reads hit the map (O(1)), seek to that offset, and read one record.

in-memory hash index on-disk log +--------+-----------+ +----------------+ | u1 | offset 28 | -------> | ...set u1="C" | <- one seek, one read | u2 | offset 42 | ----+ +----------------+ +--------+-----------+ +--> | ...set u2="D" | +----------------+

This is genuinely good: writes stay append-cheap, reads are a single seek. But it has two hard limits baked into its shape, and naming them is the point of the exercise.

Limit 1 · keys must fit in RAM

The hash map holds every key. 1 billion keys at ~64 bytes of map overhead each is ~64 GB of RAM just for the index. When your key space outgrows memory, this engine simply cannot run. Bitcask is brilliant when keys are few and values churn fast (e.g. a session store), and useless for a huge sparse key space.

Limit 2 · no range scans

A hash scatters keys to random buckets, destroying order. get(u1) is fast, but "all keys between 2024-01 and 2024-03" or "the next 100 keys after X" requires scanning everything. Any range query, prefix query, or sorted iteration is impossible. This single limitation is what motivates the B-tree in §5.

3 · Compaction: keeping the log from eating the disk

An append-only log never deletes, so it grows without bound — every set(u1, ...) leaves the old value lying in the file forever. Compaction is the cleanup process that reclaims that space: it reads old log segments (the log is broken into fixed-size files), keeps only the latest value for each key, and writes a fresh, smaller segment, then deletes the originals.

before compaction (one segment, lots of dead history) [ u1="A" | u2="B" | u1="C" | u2="D" | u1="E" | u3="F" ] dead dead dead keep keep keep after compaction (only the live value of each key survives) [ u1="E" | u2="D" | u3="F" ]

Compaction runs in the background on immutable old segments while new writes keep flowing to the current segment, so it never blocks the write path. This is the same "write sequentially now, clean up history later" bet that the LSM tree (lesson 04) makes its entire architecture out of — compaction is the bridge concept between this lesson and the next. The cost it introduces is real, though: compaction consumes disk bandwidth and CPU, and if it falls behind the write rate, dead data piles up and space balloons — a failure mode lesson 04 explores as compaction debt.

4 · The write-ahead log (WAL): the unifying abstraction

So far the log was the database. But even databases that store data in mutable, overwrite-in-place structures (like the B-tree below) keep a log too — for a different reason. Picture overwriting a B-tree page in place when the power dies halfway through the page write. You don't get the old page or the new page; you get a torn page — half old bytes, half new — and the on-disk tree is corrupt. There is no record of what you intended, so recovery is guesswork.

The write-ahead log (WAL) fixes this with one rule: before mutating any page, append a record describing the intended change to a sequential log and flush it. The mutation happens only after the intent is durable. The name says it: you write ahead to the log first.

write request | v (1) append intent to WAL --[fsync]--> durable, ordered record of "what I'm about to do" | v (2) mutate the page(s) in place (B-tree page, etc.) | v (3) acknowledge the write to the client crash between (1) and (2)? -> on restart, REPLAY the WAL: committed-but-unapplied changes are re-done; incomplete transactions are rolled back. The on-disk pages can never be left in a state the WAL can't repair.

Now the crucial move, and the reason this concept lives here and gets linked back to for the rest of the track: that same ordered, durable log is reused everywhere. It is not just a crash-recovery trick — it is the canonical "ordered durable changes" abstraction, and at least four systems are literally the same log read by a different consumer:

→Crash recovery — replay the WAL on restart to repair partial page writes (this lesson).

→Replication stream — ship the same log to follower replicas; they replay it to stay in sync (lesson 08, the replication log).

→Change data capture (CDC) — let downstream systems (search indexes, caches, data lakes) subscribe to the log to learn about every change (lesson 19).

→Audit trail / event source — the ordered log is the history; replaying a prefix reconstructs any past state (lesson 20).

Once you can see "an ordered log of durable changes, with current state as a replay of it," you will recognize the same shape inside PostgreSQL's WAL, MySQL's binlog, Kafka topics, RocksDB, event sourcing, and ML model/checkpoint registries that log every artifact write. We taught it once, here; later lessons will link back rather than re-derive it.

5 · B-trees: sorted pages, cheap reads and ranges, costly writes

The hash index couldn't do range scans because it threw away order. The B-tree — the index under essentially every relational database (PostgreSQL, MySQL/InnoDB, SQLite) — keeps keys sorted, which buys back range queries and bounds memory at the same time.

A B-tree breaks the key space into fixed-size pages (a page is the unit of disk I/O the engine reads and writes as one block, typically 4 KB or 8 KB). Pages form a shallow, wide tree. The root page holds keys plus pointers to child pages; each child narrows the range further; the bottom leaf pages hold the actual values (or pointers to them). The branching factor B is how many child pointers fit in one page — and because a 4 KB page holds hundreds of key+pointer entries, B is large (often 100–1000), which is why the tree is only a handful of levels deep even for enormous tables.

[ root page: keys split into B ranges ] / | \ [ ...100s of keys ] [ ...100s ] ... [ ...100s of keys ] <- internal pages / | \ [leaf] ... [leaf] ... [leaf] <- values live here lookup(k): start at root, binary-search this page for the child range containing k, read that child page, repeat down to a leaf. pages read = tree height = ~log_B(N).

Worked number — how many pages a lookup touches

Take a table of N = 100,000,000 keys with branching factor B = 500. The number of leaf-reachable slots after h levels is B^h:
• 500^1 = 500
• 500^2 = 250,000
• 500^3 = 125,000,000 ≥ 100M → 3 levels suffice (4 with the root counted, depending on how you count).
So a point lookup in 100 million keys reads only about 3–4 pages from the tree. In practice the root and upper internal pages stay cached in RAM, so a cold lookup is often just one disk read at the leaf. That O(log) page count — staying flat as N grows by orders of magnitude — is exactly why B-trees scale. And because keys are sorted, a range scan finds the start key in those ~3 reads, then walks leaf pages left-to-right sequentially — the query the hash index could never do.

So reads are cheap and ranges are cheap. The bill arrives at write time, and it has a name.

The defining cost: write amplification

Write amplification is the ratio of bytes actually written to disk to the bytes of logical data the user changed. A B-tree is bad at it. Update one 200-byte record and the engine must:

Rewrite a whole page. Pages are the unit of I/O, so changing one record dirties and rewrites its entire ~4 KB page. That alone is a 4096 / 200 ≈ 20× amplification for the data page.
Possibly split pages. If an insert overflows a full leaf, the engine splits it into two half-full pages and updates the parent's pointers — sometimes cascading splits up the tree.
Update every secondary index. A secondary index is an additional B-tree keyed on some other column (e.g. an index on email so you can look users up by email). Each one is its own tree, so a single row write that touches indexed columns dirties a page in each index. Three secondary indexes → up to four trees mutated per write.
Write the WAL first (§4), so the same change is also appended to the log for durability.

Net: one tiny logical update can become tens of kilobytes of physical writes across several random page locations. Contrast the append log of §1, where that same update is one sequential 200-byte append. That gap — sequential append vs. random in-place page rewrites — is the central tension lesson 04 resolves with the LSM tree.

The takeaway is not that B-trees are worse. They pay more at write time to make point reads, range scans, and transactional in-place updates simple, predictable, and low-latency — exactly what OLTP workloads need. A B-tree is the right default when you need stable read latency and ranges; the LSM tree (lesson 04) trades the other direction for write-heavy ingest.

6 · The trade-offs, side by side

Choice	Buys	Costs
Append-only log + hash index	Fastest possible durable writes (sequential append); O(1) point reads via one seek	All keys must fit in RAM; no range scans; needs background compaction to bound disk
B-tree primary index	O(log) point reads (~3–4 pages for 100M keys); efficient range scans; mature in-place transactions	Write amplification: page rewrites, page splits, random I/O
Each additional secondary index	Makes another access pattern (lookup by that column) cheap	Every write that touches it must update one more B-tree — more write amplification
Write-ahead log (WAL)	Crash recovery from torn page writes; doubles as replication stream, CDC source, and audit trail	Extra sequential write per change; log must be managed, fsync'd, and truncated

Failure modes

No index, so reads scan history. A bare log is write-only in practice; a point read becomes a full file scan. Always pair the log with a read structure.
Hash index outgrows RAM. The key set silently exceeds memory and the engine thrashes or refuses to start. Hash indexes only fit bounded key spaces.
Compaction falls behind. Writes outrun the cleaner, dead versions accumulate, and disk usage balloons until the volume fills (revisited as compaction debt in lesson 04).
Skipping the WAL. A crash mid-page-write leaves a torn page and an unrecoverable tree; recovery becomes guesswork. The WAL exists precisely so partial writes are always repairable.
Index sprawl. Adding "just one more" secondary index to speed a query quietly multiplies write amplification on the hot write path; the write slowdown shows up far from the index you added.

Decision checklist

Is the dominant access pattern point lookups, range scans, or write throughput? (Lesson 06 vocabulary.)
Does the key set fit in RAM? If not, a hash index is out — you need a B-tree or LSM.
Do you need range/prefix/sorted queries? If yes, the structure must keep keys ordered (B-tree, LSM).
Is there a write-ahead log, and is it fsync'd before pages are mutated and acknowledged?
Could the same WAL be reused as your replication / CDC / audit source instead of building a second pipeline (lessons 08, 19, 20)?
How many secondary indexes does each write maintain — and is that write amplification acceptable on the hot path?
Is compaction (or page reclamation) keeping pace with the write rate, with headroom for bursts?

Checkpoint exercise

Try it

Design the storage for a feature store's online layer: it serves the latest feature vector for each entity ID to a model at serving time (point lookups, very high write churn, no range queries, key set in the tens of millions). (1) Would you reach for an append-log + hash index, a B-tree, or something else — and what assumption about the key set decides it? (2) Sketch the write path including the WAL, and say what a crash mid-write must not be able to corrupt. (3) Now add a second requirement: an offline job must read every feature change in order to rebuild a training table. Show how the WAL you already have becomes that feed for free, without a second write pipeline. (4) Estimate, for 50M keys and a B-tree with branching factor 400, how many pages a cold point lookup touches.

Where this points next

The B-tree's whole cost was write amplification: in-place page rewrites scattered across the disk, every secondary index updated per write. Lesson 04 asks the obvious question — what if we refuse to overwrite pages at all and lean entirely into the append from §1? The LSM tree does exactly that: writes go to an in-memory sorted buffer plus a WAL, flush to immutable sorted files, and get merged by the same compaction you just met — turning random writes back into sequential ones at the price of read amplification. The same lesson then turns the table sideways into columnar storage for analytics, where bytes are laid out by column so a scan reads only the fields a query asks for. Both are direct descendants of the log you built here.

Where is truth?

Inside a single storage engine the answer is unusually crisp: the system of record is the ordered, durable log / WAL — intent is fsync'd there before any page is touched, so it is the one thing a crash cannot lose. Everything else is a derived copy / view rebuilt from it: the in-memory hash map, the B-tree pages, every secondary index, and current materialized state are all replays of the log. Freshness budget: the gap between a committed WAL record and its application to the pages (zero at acknowledgement time, since the WAL is flushed first). Owner: the storage engine; the WAL's fsync-before-mutate rule is the contract. Deletion path: append a delete/overwrite record to the log, then let compaction physically reclaim the superseded bytes. Reconciliation / repair: on restart, replay the WAL front to back — re-do committed-but-unapplied changes, roll back incomplete ones — so pages can never be left in a state the log cannot repair. Evidence it is correct: per-record length/checksum fields that detect a torn final write and discard it.

Takeaway

A storage engine trades write cost, read cost, space, and recovery time, and the append-only log is the primitive that makes durable change cheap: sequential append is the fastest durable write, and a crash is just a replay. Reads then demand an index — and every index speeds reads while slowing writes. A hash index gives O(1) point lookups but needs all keys in RAM and can't do ranges; compaction keeps its log bounded. The write-ahead log generalizes this: write intent sequentially before mutating pages so a torn page is always recoverable — and that one ordered, durable log is reused as the replication stream, CDC source, and audit trail across the rest of this track. The B-tree keeps keys sorted in fixed-size pages: a lookup in 100M keys reads only ~3–4 pages and ranges are cheap, but the bill is write amplification — a one-record update rewrites a whole page, may split pages, and dirties every secondary index. Lesson 04's LSM tree pays that bill the other way.

Interview prompts

Why is appending to a log the cheapest durable write? (§1 — it is purely sequential I/O, which is 10×+ faster than random I/O on both spinning disks and SSDs; you always write to one place, the end, and recovery is a front-to-back replay.)
You have a bare append-only log. Why are reads a problem, and what fixes them? (§2 — finding the latest value means scanning the whole file; an index maps key→location so you jump straight there. But every index slows writes, since each write must update it too.)
When does a Bitcask-style hash index break down? (§2 — two hard limits: all keys must fit in RAM, so a huge key space is impossible; and it can't do range/prefix/sorted scans because hashing destroys order.)
Why does even a B-tree database keep a write-ahead log? (§4 — overwriting a page in place can be torn by a crash, corrupting the tree; writing intent to a sequential log first makes every partial write recoverable via replay.)
What does it mean that the WAL is a "unifying abstraction"? (§4 — the same ordered durable log is reused as crash recovery, the replication stream (08), the CDC feed (19), and the audit/event-source history (20); current state is a replay of it.)
How many pages does a B-tree point lookup touch, and why does that matter? (§5 — about log_B(N): for 100M keys at B=500 that's ~3–4 pages, and it stays flat as N grows, with upper levels cached — so reads scale to huge tables.)
What is write amplification, and why is it the B-tree's defining cost? (§5 — bytes written to disk vs. bytes the user changed; one tiny update rewrites a whole ~4 KB page, may split pages, and dirties every secondary index plus the WAL, versus one sequential append in a log.)