4. Storage and Retrieval

"A computer does not primarily compute in the sense of doing arithmetic. […] They primarily are filing systems." — Richard Feynman

Ch 3 was the user's view (what format you give the database, what interface you query it through). Ch 4 is the database's view: how it stores what you give it, and how it finds it again.

Why you should care even though you'll never write a storage engine: you must select the right one from many available, and to configure it to perform well on your workload you need a rough idea of what it's doing under the hood.

The chapter's map:

Figure 4.0.1The chapter's map

Sections

4.1
The world's simplest databaseReal databases add: handling concurrent writes, reclaiming disk space so the log doesn't grow forever, and handling partially written records when recovering from a crash.
4.26
Log-Structured StorageKeep an in-memory hash map: key → byte offset of its most recent value in the log.
4.32
B-Trees
4.41
Comparing B-Trees and LSM-Trees
4.51
Secondary indexes and where values liveBoth B-trees and log-structured storage can implement an index.
4.6
Keeping everything in memoryEverything so far is an answer to the limitations of disks.
4.78
Data Storage for AnalyticsData warehouses are usually relational, because SQL fits analytical queries well, and many graphical tools generate SQL and support drill-down and slicing and dicing.
4.85
Multidimensional and Full-Text IndexesImplemented in Facebook's Faiss (several variants of each) and PostgreSQL's pgvector (both).
4.9Deep dives1
Technology deep dives
4.10Failure catalog
Production failure catalog for this chapter
4.11Decision sheet
Decision cheat sheetWrite-heavy, high ingest, sequential-write-friendly, want cheap snapshots and lower write amplification → LSM.
4.12Worked examples
Worked examplesLeaf pages = 500³ = 125,000,000. Capacity = 125,000,000 × 4 KiB = 500 GB of leaf pages; the book's figure of ~250 TB assumes 500⁴ leaf entries' worth of addressable data (4 levels…
4.13Self-test
Self-test
4.14Terminology
Terminology introduced here
4.15Forward links
Forward links