Storage and Retrieval

In one sentence

Chapter 2 asked "what does data look like from the application's point of view"; Chapter 3 drops one level and asks the harder question: how does a database actually write data to disk, and how does it find it again? The chapter is framed by two oppositions—storage engines come in two great families, log-structured (LSM-tree) and page-oriented (B-tree); and workloads come in two, transaction processing (OLTP) and analytics (OLAP), the latter giving rise to column-oriented storage. Understand what happens inside the engine and you can finally pick—and tune—the right database.

Glossary

Where it sits

This chapter is still in Part I, "Foundations of Data Systems." Chapter 2 looks up—how you model data as relational / document / graph; Chapter 3 looks down—how that data is actually laid out and found on disk, and Chapter 4 follows with "how to encode it into bytes without breaking compatibility." In real life this chapter is exactly the decisions you make daily: should I use MySQL or Cassandra? Why did this analytics query scan for ages? Should this table get another index? Without understanding the engine, these are all guesswork.

What this chapter is solving

You probably won't hand-write a storage engine, but you must pick one, and know how to tune it. The cost of picking wrong is real: a database tuned for transactions is unusably slow at analytics, and vice versa. To choose wisely you need a rough but correct mental model of "what happens under the lid."

The starting point of that model is an almost absurdly simple fact: the simplest database is just appending to the end of a file. Writing is O(1)—append a line, absurdly fast; but reading is O(n)—finding one record means scanning top to bottom, which collapses as data grows. Hence the index, and the iron law that runs through the whole chapter: every index trades slower writes for faster reads. This is what the chapter answers: how real engines index, and which side of that ledger each one lands on.

Core content, in depth

① The essence of an index: a derived structure that trades writes for reads

DDIA opens with a few lines of shell: db_set appends key,value to a file, db_get uses grep to find the last one from the top. Writing is fast, reading is terrible. To rescue reads you maintain an index—an extra structure derived from the primary data. The core trade-off fits in one line: an index makes reads faster but writes slower, because every write must also update every relevant index. So databases don't index everything by default—which columns to index is a choice you make.

② The log-structured family: hash index → SSTable → LSM-tree

The most naive index is an in-memory hash map: key → the byte offset of that key in the log file. Write: append to the log, update the map; read: look up the offset, seek straight there. This is Bitcask (Riak's default engine). Fast, but with two hard limits: the hash map must fit entirely in memory; and keys are unordered, so range queries ("find all keys between 100 and 200") are impossible. And the log only grows, so it eventually fills the disk—the fix is to break it into segments and run compaction in the background: merge old segments, keep only the latest value per key, delete via a tombstone marker.

Sort each segment by key and it becomes an SSTable (Sorted String Table). That one property—being sorted—buys three big things: first, merging streams like merge sort, without reading whole segments into memory; second, the index can be sparse—one key every few KB is enough, so a read locates the rough range then scans; third, records in a range can be compressed as a block before hitting disk, saving space and bandwidth.

But writes arrive out of order—how do you keep disk sorted? The answer is tiering: keep an in-memory sorted balanced tree (the memtable—a red-black tree or skip list); writes go into the memtable first; when it grows past a few MB, the whole thing is flushed to disk as a sorted SSTable segment and never modified again. Reads check the memtable, then scan SSTables newest to oldest. The background continuously compacts small segments into bigger ones. To keep the memtable from being lost in a crash, a WAL is appended before each memtable write.

This structure is the LSM-tree (Log-Structured Merge-Tree), from Patrick O'Neil et al.'s 1996 paper. LevelDB, RocksDB, Cassandra, HBase, ScyllaDB are all this, and the full-text engine Lucene's term dictionary uses the same idea. A key optimization is the Bloom filter: an extremely memory-thrifty probabilistic structure that can quickly say "this key is definitely not in that segment," skipping a doomed disk read—especially handy when looking up keys that don't exist.

③ The page-oriented family: B-tree, the industry standard

The B-tree is the most widely used, most standard index—almost every relational database and many non-relational ones use it. Its approach is the opposite of LSM: instead of chopping the database into variable-length log segments to append, it chops it into fixed-size pages (traditionally 4 KB) and reads/writes one whole page at a time. Pages reference each other by disk address—like memory pointers, only pointing at disk. One page is the root, holding some keys and pointers to child pages; follow the pointers level by level down to a leaf page holding the actual value.

The number of child pages per page is the branching factor, typically several hundred—so the tree is short and fat, with depth O(log n). DDIA's figure is vivid: branching factor 500, 4 KB pages, and 4 levels can store 256 TB—any record is at most 4 page-reads away. Changing data is an update in place: find the leaf page, edit, and write the whole page back to its original spot; if a page is full it splits into two and the parent's pointers are updated. This is a sharp contrast to LSM's "never touch old files."

Update-in-place has a reliability hazard: a page split rewrites several pages, and a crash midway can leave it half-written and corrupt the tree. The B-tree's answer is also a WAL (here called a redo log)—before changing a page, append the change to the log, then replay the log to recover after a crash. Multiple threads touching the same tree also need latches (lightweight locks) to prevent reading a half-written page.

④ Other indexes: secondary, clustered, covering, multi-column, in-memory

The above is the primary-key index; in practice there's a family of variants, each explained on sight: a secondary index builds a directory on a non-primary column (e.g., look up a user by email), and both LSM and B-tree support them. A clustered index stuffs the entire row right into the index's leaf page, so a lookup gets the row with no second hop—MySQL's InnoDB primary key works this way. A covering index carries a few extra columns so some queries are "index-only," never touching the main table. A multi-column (concatenated) index combines several columns into one key; geospatial queries use a specialized R-tree. And there are in-memory databases (Redis, Memcached, VoltDB): they're fast not mainly because they "avoid reading disk," but because they skip the overhead of "encoding in-memory structures into bytes for durability."

⑤ A different world: OLTP vs OLAP, and column storage

Everything above is OLTP—read/write a few records at a time, point-lookup by key, powering your orders and transfers. But companies have another job: OLAP (analytics)—one query scans millions or billions of rows yet cares about only a few columns (e.g., "total sales by region, by month"). Running analytics on OLTP row storage means, just to average one column, hauling every whole row off disk and throwing most of it away—hugely wasteful. So enterprises typically build a separate data warehouse, using ETL (extract-transform-load) to copy operational data over for analytics, often in a star schema (a central fact table with dimension tables around it).

The warehouse's killer feature is column-oriented storage: instead of "all columns of one row stored adjacently," it's "all rows of one column stored adjacently." An analytics query reads only the columns it needs, so disk I/O drops immediately. Better still, values in one column are highly similar (a "city" column repeats just a few hundred values), so compression is excellent—DDIA's bitmap encoding plus run-length encoding often squeezes a column to a fraction of its size, and combined with CPU vectorized batch processing, analytics throughput can beat row storage by one to two orders of magnitude. The cost is that writes get awkward: inserting a row must be split and written into every column, so column storage is used almost only for "bulk load, heavy query" analytics, never for frequently-changing online business.

Key trade-offs and choices

The soul of this chapter is three trade-offs. First the two engine families—LSM-tree vs B-tree—the one table you most want in your head when choosing a database:

Table 1 · LSM-tree (log-structured) vs B-tree (page-oriented)

Second is the workload—row-oriented OLTP vs column-oriented OLAP—essentially "point-lookup a few records" vs "scan huge rows, take a few columns":

Table 2 · Row-oriented OLTP vs column-oriented OLAP

Third runs throughout: the trade-off of an index itself—one more index means faster reads, slower writes, and more space. So don't index every column; index the ones actually used as query conditions. The industry sums this up as the RUM conjecture: read amplification, write (update) amplification, and memory (space) amplification cannot all be optimal at once—optimizing one usually sacrifices the other two. LSM lowers write amplification but raises read amplification, B-tree the reverse—a living illustration of the conjecture.

Why it matters / real systems

This chapter hands you a pair of X-ray glasses: see Cassandra / HBase / RocksDB and you know it's LSM underneath—high write throughput, space-lean, but compaction steals bandwidth; see PostgreSQL / MySQL InnoDB and you know it's a B-tree—steady reads, strong transactions, update-in-place; see Redshift / BigQuery / Snowflake / ClickHouse and you know it's columnar, built to "scan huge, compute a few columns," not for high-frequency point lookups. When an interview asks "why Cassandra for write-heavy, why a separate warehouse for analytics," the answer lives in these three trade-offs. And these claims aren't armchair theory—big companies have backed them with public, checkable practice:

Pitfalls and controversies

• "LSM is always faster than B-tree"—wrong. LSM has high write throughput, but background compaction competes with foreground reads/writes for disk bandwidth, causing high-percentile (p99) latency spikes; under some workloads write amplification is actually worse. B-tree latency is more predictable. Choosing depends on whether you fear "slow on average" or "occasional stall" more.
• "More indexes is better"—wrong. Every index trades write speed and space for read speed. Indexing columns rarely used in queries only slows writes and wastes space.
• Running analytics directly on an OLTP database. Big reports on the operational primary both drag down live transactions and run slow—which is exactly why data warehouses and column storage exist. Don't mix them.
• Misreading in-memory databases as "fast because they skip disk reads." The bigger win is skipping the "encode/decode for durability" overhead; some in-memory databases can even manage datasets larger than memory.
• Time limits (2017). Since then NVMe SSDs have largely flattened the random-write penalty, key-value separation (e.g., WiscKey) has cut LSM write amplification, and "learned indexes" explore replacing B-trees with models; but the "log-structured vs page-oriented, row vs column" taxonomy remains solid.
• SSD lifespan. LSM's repeated compaction amplifies writes and wears flash; but a B-tree also overwrites whole pages each time—neither is free, weigh it against your write pattern.

Takeaways