Part I of Database Internals is about one node. Before replication, consensus or sharding enter the picture, a database has to take bytes from a client, put them on a disk in a way that survives a crash, and find them again faster than a linear scan. The component that does this is the storage engine, and the seven chapters in this part are a bottom-up tour of how a modern one is built.

Almost every storage interview question (why is this write slow, why does this index help, what happens on crash, why does Cassandra compact) is answered by material from these chapters. This page maps the part.

What a storage engine is

A DBMS does many things: it parses queries, plans them, checks permissions, talks to clients over the network. The storage engine is the layer at the bottom that owns the data: it implements create, read, update and delete on records, keeps indexes consistent with data, caches pages in memory, and makes committed changes durable.

Petrov treats the storage engine as a replaceable component, and real systems agree. MySQL lets you choose an engine per table (ENGINE = InnoDB, MyISAM, or MyRocks, a RocksDB-backed engine), MongoDB swapped MMAPv1 for WiredTiger, and CockroachDB, TiDB and YugabyteDB are coordination layers over an embedded key-value engine such as RocksDB or Pebble.

Two families dominate. Mutable, in-place B-trees (PostgreSQL, InnoDB, SQLite, WiredTiger) keep data sorted on disk and update pages where they live. Immutable, log-structured engines (LevelDB, RocksDB, Cassandra, HBase, Bigtable) append and periodically merge. Almost every trade-off in Part I comes back to that split: read amplification versus write amplification versus space amplification, and where you pay for ordering.

How the chapters build on each other

Chapter	Topic	What it gives you
1 Introduction and Overview	DBMS architecture, memory vs disk, row vs column, data and index files, buffering/immutability/ordering	The vocabulary and the three axes used to classify everything that follows
2 B-Tree Basics	Why binary trees fail on disk, block devices, B-tree structure, lookup, split, merge	The canonical mutable on-disk structure
3 File Formats	Binary encoding, slotted pages, variable-size records, checksums	How a B-tree node (or any page) is actually laid out in bytes
4 Implementing B-Trees	Page headers, sibling links, rightmost pointers, overflow pages, binary search, rebalancing, compaction	The engineering that turns the textbook tree into a production one
5 Transaction Processing and Recovery	Buffer manager, page replacement, WAL, ARIES, steal/force, locking, latches	How a B-tree survives crashes and concurrent access
6 B-Tree Variants	Copy-on-write, lazy B-trees (WiredTiger, LA-trees), FD-trees, Bw-trees, cache-oblivious trees	What changes when you relax in-place updates
7 Log-Structured Storage	LSM trees, memtables, SSTables, compaction, Bloom filters, RUM conjecture	The immutable alternative and the cost model to compare both

The dependency chain is tight. Chapter 1 defines terms (primary and secondary index, clustered index, buffer manager) that every later chapter uses without re-explaining. Chapter 2 presents the B-tree as an abstract data structure, deliberately ignoring bytes. Chapter 3 fills in the bytes: once you know how a slotted page stores variable-length cells, Chapter 4's discussion of overflow pages, sibling pointers and in-page binary search makes sense. Chapter 5 then wraps the structure in a transaction manager, a buffer pool and a write-ahead log so that a crash mid-split cannot corrupt it.

Chapters 6 and 7 are the payoff. Chapter 6 asks which B-tree assumptions can be dropped: copy-on-write trees (LMDB) avoid in-place writes entirely, lazy B-trees buffer updates in memory, Bw-trees go latch-free with a mapping table and delta chains. Chapter 7 goes further and drops in-place mutation altogether, arriving at the LSM tree. Only after you have seen both can you reason about the RUM conjecture: you cannot minimise read, update and memory overhead at once, so every engine picks which two to favour.

Recommended reading order

Read the chapters in numerical order the first time. Petrov wrote them sequentially and the later ones assume the earlier vocabulary.

If you are short on time and preparing for a system-design interview, the minimum viable path is Chapter 1 (architecture and the three axes), Chapter 2 (B-tree mechanics), the WAL and buffer-manager sections of Chapter 5, and all of Chapter 7. That subset lets you compare PostgreSQL to RocksDB intelligently, which is the storage question that comes up most.

For a database or infrastructure engineering role, do not skip Chapters 3 and 4: page layout, slotted pages, overflow handling and checksums separate people who have used databases from people who could build one.

Chapter 6 is the most skippable on a first pass; return to it when you want to understand WiredTiger (MongoDB), LMDB or the Hekaton/Bw-tree lineage.

How this part connects to Part II

Part II (distributed systems) treats each node as a black box that stores and retrieves keys; everything inside that box is Part I. Replication logs rely on the write-ahead log from Chapter 5, anti-entropy with Merkle trees assumes the sorted immutable files from Chapter 7, and the per-node latency of a quorum read is the read amplification analysed here.

What interviewers tend to ask from this part

• "Why does a database use a B-tree instead of a binary search tree or a hash table?" Fanout, height and locality (Chapter 2), plus ordered range scans that hashes cannot give.
• "Walk me through what happens when I write a row." Parser to planner to executor to storage engine; buffer pool page, WAL record, dirty page, later flush (Chapters 1 and 5).
• "What is write amplification and where does it come from?" SSD flash translation, B-tree page rewrites, LSM compaction (Chapters 2 and 7).
• "Compare B-trees and LSM trees for a write-heavy workload." The classic. Chapter 7's RUM framing gives you a structured answer rather than a list of adjectives.
• "How does a database recover after a crash?" WAL, redo and undo, steal/no-steal and force/no-force, checkpoints (Chapter 5).
• "What is a clustered index, and why does InnoDB's secondary index store the primary key?" Chapter 1's data-file and index-file section.
• "How would you store variable-length records in a fixed-size page?" Slotted pages (Chapter 3).
• "Is Cassandra (or HBase) a column store?" No; wide column stores are row-oriented at the storage level. Chapter 1 explains the distinction.

Further reading

• Database Internals, Part I introduction and Chapters 1–7.
• Goetz Graefe, "Modern B-Tree Techniques", Foundations and Trends in Databases, 2011. The deep reference behind Chapters 2, 4 and 6.
• Patrick O'Neil et al., "The Log-Structured Merge-Tree (LSM-Tree)", Acta Informatica, 1996. The original paper behind Chapter 7.
• Manos Athanassoulis et al., "Designing Access Methods: The RUM Conjecture", EDBT 2016.
• Joseph Hellerstein, Michael Stonebraker and James Hamilton, "Architecture of a Database System", Foundations and Trends in Databases, 2007. The best companion to Chapter 1.
• RocksDB wiki, https://github.com/facebook/rocksdb/wiki
• PostgreSQL documentation, "Database Physical Storage" chapter, https://www.postgresql.org/docs/current/storage.html