Module 2: Storage Engines & Indexing: Worked Examples
Example 1: Recover an Append-Only Store After a Torn Tail
Problem. A key-value store appends length-prefixed records [length][crc][key][value]. A crash occurs halfway through the final record.
Wrong first attempt. Trust the file length and parse until EOF. The partial length or payload can be interpreted as valid bytes and poison recovery.
Correct reasoning. Recovery advances only after validating a complete header, bounded length, complete payload, and checksum. It records the last valid offset and truncates the invalid tail. Earlier records remain authoritative; later versions of a key supersede earlier ones during index rebuild.
Why it works. Append-only recovery needs a precise commit boundary. A checksum detects partial or corrupted records; truncation restores the invariant that every retained record is complete.
Transfer question. Why is a checksum insufficient if the OS acknowledges a write but the drive reorders it across a metadata update?
Example 2: B+ Tree or LSM Tree for Two Workloads
Problem. Workload A performs frequent point updates and range scans. Workload B ingests telemetry at high write volume and usually queries recent time windows.
Wrong first attempt. Choose LSM because writes are “always faster.” Compaction can amplify writes and create latency spikes; range reads may consult several runs and Bloom filters.
Correct reasoning. A B+ tree is a strong default for A because ordered leaves support stable range scans and in-place page updates. An LSM tree may suit B because sequential memtable flushes absorb writes, provided compaction bandwidth, read amplification, and retention are explicitly budgeted.
| Evidence | B+ tree | LSM tree |
|---|---|---|
| Write path | Page lookup and update | WAL + memtable, later compaction |
| Range read | Ordered leaf walk | Merge across overlapping runs |
| Main operational risk | Random I/O/page splits | Compaction debt and amplification |
Transfer question. How does an SSD change constants without removing either structure’s amplification tradeoffs?
Example 3: Estimate Index Fanout
For an 8 KiB internal B+ tree page with 16-byte keys, 8-byte child pointers, and about 128 bytes of page overhead, an approximate fanout is floor((8192-128)/(16+8)) = 336. Three internal levels can address roughly 336^3, over 37 million leaf ranges.
The estimate explains why database indexes remain shallow. It is not an exact implementation claim: slot arrays, prefix compression, fill factor, and variable-length keys change the result.
Transfer question. Recalculate for 64-byte keys and explain the latency consequence.
Completion Standard
- Implement recovery that rejects a torn final record.
- Defend a B+ tree/LSM choice using read, write, and space amplification.
- Produce a fanout estimate and list the assumptions that make it approximate.