Book notes · Alex Petrov

Database Internals

Concise, chapter-by-chapter notes in the order of the book, with side learnings, the most surprising takeaways, and the open questions each chapter left behind.

16 chapters about 5 hours end to end

Start reading

1Storage engines

How a single node stores, indexes, recovers and compacts data.

8 chapters

Overview 5 minStorage engines: an overviewWhat a storage engine is, how the seven storage chapters build on each other, the order to read them in, and what interviewers ask from this partRead
Chapter 1 20 minIntroduction and OverviewDBMS architecture, memory vs disk-based stores, column vs row layout, data and index files, and buffering, immutability and ordering as the axes that classify storage enginesRead
Chapter 2 20 minB-Tree BasicsWhy binary search trees fail on disk, how HDDs and SSDs shape page-based design, and how B-trees do lookups, inserts, splits, deletes and mergesRead
Chapter 3 20 minFile FormatsBinary encoding, page layout and slotted pages, variable-size records, fragmentation and defragmentation, versioning, and checksums: how a B-tree node becomes bytes on diskRead
Chapter 4 20 minImplementing B-TreesPage headers, sibling links, high keys and overflow pages; in-node binary search; propagating splits with breadcrumbs; rebalancing, right-only appends, compression and vacuumRead
Chapter 5 20 minTransaction Processing and RecoveryPage cache and eviction policies, write-ahead logging and ARIES recovery, steal/force, isolation levels and anomalies, OCC, MVCC, 2PL, deadlocks, latches and Blink-treesRead
Chapter 6 20 minB-Tree VariantsCopy-on-write B-trees (LMDB), lazy B-trees (WiredTiger, LA-tree), FD-trees, latch-free Bw-trees and cache-oblivious layouts: what each fixes and what it costsRead
Chapter 7 20 minLog-Structured StorageLSM trees end to end: memtables, SSTables, tombstones, merge iteration, leveled vs size-tiered vs time-window compaction, Bloom filters, RUM, Bitcask, WiscKey, SSD log stackingRead

2Distributed systems

How many nodes detect failure, pick leaders, replicate and agree.

8 chapters

Database Internals

1Storage engines

2Distributed systems

Search

Database Internals

1Storage engines

2Distributed systems