Chapter 2: How a Database Actually Stores Your Data

Curriculum: Distributed Systems from First Principles Chapter: 2 of 24 Part: 1 — Physical Foundation Prerequisites: Chapter 1 (latency numbers, memory hierarchy, sequential vs random I/O) Estimated reading time: 75–90 minutes

Opening

You've been writing SQL for years. You know that SELECT * FROM users WHERE email = 'alice@example.com' returns a row. What you probably don't know is what Postgres physically does to make that happen — how it opens files, how it reads binary data, how it decides whether to scan everything or jump directly to what you asked for, and exactly why the difference between those two choices can be the difference between an 8-millisecond query and a 17-second one. After this chapter, SQL will feel different. You'll write a query and hear, in the background, the sound of pages moving from disk to memory and back. You'll understand why adding an index to a frequently-queried column is not a performance "trick" — it's a response to a precise physical cost that you can calculate. Chapter 1 gave you the cost of the operations. This chapter shows you where those operations actually occur inside a database.

Part 1: Your Rows Don't Live Where You Think They Do

When you run INSERT INTO users (id, name, email) VALUES (1, 'Alice', 'alice@example.com'), where does that row go?

Your instinct might be: "into the database file, somehow." That's correct but so vague as to be useless. The actual answer is more specific and more interesting.

Postgres stores every table as one or more files on disk. For a table called users in your database, there's a file on disk — somewhere in the Postgres data directory — that contains every row in that table. But Postgres never reads individual rows directly from that file. It doesn't open the file, seek to the row, and read exactly the bytes you asked for. Instead, it reads the file in fixed-size chunks called pages.

A page in Postgres is 8 kilobytes. That's 8,192 bytes. Postgres reads and writes exactly one page at a time — never half a page, never three rows, never exactly the bytes for your specific row. The page is the fundamental unit of all I/O. When Postgres needs any piece of data, it reads the whole 8KB page that contains it.

Why 8KB? Because the operating system also manages disk I/O in chunks — typically 4KB on most Linux systems, sometimes 8KB — called OS pages. Database pages are designed to align with OS pages so that one database read maps to a small, fixed number of OS reads. This alignment avoids partial-page reads that would be both slow and complex to manage. The 8KB default in Postgres is a choice made decades ago that has held up well, though it can be changed at compile time (most people don't).

This page-based I/O has a significant consequence: if you want to read one row, you must read the entire 8KB page that contains it, even if all you needed was 100 bytes. This is not a design flaw — it's a deliberate alignment with how storage hardware works. Both SSDs and HDDs operate most efficiently when reading aligned, fixed-size blocks. Partial reads would be slower and require more complex handling.

Part 2: The Layout of a Single Page

Let's look inside one 8KB page. Understanding its layout explains a lot of seemingly mysterious database behaviour.

A Postgres page has four sections:

+----------------------------------+  <- byte 0
|  Page Header (24 bytes)          |
|  (LSN, checksum, free space ptr) |
+----------------------------------+
|  Item Pointers (4 bytes each)    |
|  [ptr1][ptr2][ptr3]...           |
|                                  |
|       (free space grows here)    |
|                                  |
|  ...row3][row2][row1]            |
|  Tuples (rows, variable size)    |
+----------------------------------+  <- byte 8191

The page header is 24 bytes at the top. It contains: the LSN (Log Sequence Number — a pointer into the write-ahead log, which we'll see in Chapter 5), a checksum for detecting corruption, and a pointer to the start of the free space.

Below the header is a growing array of item pointers — each one is 4 bytes and contains an offset and length pointing to a specific row's data within this page. New item pointers are added left-to-right.

Tuples (Postgres's word for rows) are written right-to-left from the end of the page. When you insert a new row, Postgres adds a new item pointer at the current end of the item pointer array, and writes the tuple data backwards from the end of the free space region.

The page fills from both ends toward the middle. When the item pointer array meets the tuple data region, the page is full.

Each tuple (row) in the page is not just your column values — it has its own header. The tuple header is 23 bytes and contains several fields you might never have heard of but that matter enormously:

• xmin: The transaction ID of the transaction that inserted this row.
• xmax: The transaction ID of the transaction that deleted this row (or 0 if not deleted).
• ctid: A physical pointer to the current version of this row (page number + offset).

These three fields are how Postgres implements MVCC — Multi-Version Concurrency Control — which lets multiple transactions read and write simultaneously without blocking each other. We'll explore MVCC in depth in Chapter 5. For now, just note that every row carries invisible metadata that Postgres uses for concurrency management. This metadata is part of why row storage has overhead beyond your actual column values.

Part 3: The Heap File — A Table Is Just Pages in a Sequence

A table's data lives in what Postgres calls a heap file. "Heap" here means unordered — rows are not stored in any particular sorted order. They're placed into pages wherever free space is available.

When you insert row 1, then row 2, then row 3, they end up in roughly the order they were inserted — but that's incidental, not guaranteed. When you delete a row, the space is eventually reclaimed but the page isn't immediately rewritten. When you update a row, Postgres doesn't update it in place: it marks the old version as deleted (by setting xmax on the old tuple) and writes a new version elsewhere. This is MVCC again. The consequence is that a heavily-updated table accumulates dead tuples — old row versions that are no longer visible to any active transaction — until VACUUM comes along to clean them up.

For now, the critical mental model is: a table is a flat sequence of 8KB pages, each containing some rows, in no particular order.

Table: users (1 million rows, ~200 bytes/row average)

Total data size: 1,000,000 × 200 bytes = 200 MB
Pages required: 200 MB / 8 KB = ~25,600 pages

On disk:
[page 0][page 1][page 2]...[page 25,599]
   ↓        ↓        ↓
  rows    rows     rows
(unordered within each page, pages in no sorted order)

When Postgres executes a query, it needs to figure out which pages contain the rows you asked for. How it does that is the central question of this chapter.

Part 4: The Full Table Scan — and Why It Hurts

You run this query on your SaaS product's database:

SELECT * FROM users WHERE email = 'alice@example.com';

There is no index on the email column. What does Postgres do?

It reads every single page in the heap file, from page 0 to page 25,599, and for each page it reads, it checks every row inside that page to see if the email column matches. This is called a sequential scan (Postgres calls it a Seq Scan in its query plans). It is the brute-force option — it always works, it requires no extra data structures, but it scales linearly with the size of the table.

Let's put actual numbers on this for a table with 10 million rows at 500 bytes per row:

Data size:   10,000,000 × 500 bytes = 5 GB
Pages:       5 GB / 8 KB = ~655,360 pages

Reading 655,360 pages sequentially from NVMe SSD:
  At 3 GB/s sequential throughput = 5 GB / 3 GB/s ≈ 1.7 seconds

Reading 655,360 pages randomly from NVMe SSD:
  At 100 µs per random read = 655,360 × 0.1 ms = 65 seconds

In practice, Postgres does a sequential scan sequentially — it reads pages in order, which is the faster case. So a full scan of 5 GB of data takes roughly 1.7 seconds on good hardware. That doesn't sound terrible until you remember:

• This is for one query.
• Your SaaS product might serve 500 such queries per second.
• 500 simultaneous 1.7-second full scans means you need 850 seconds of I/O bandwidth per second — you'd need hundreds of hard drives.
• That 1.7 seconds is just reading. Postgres also needs to check each of the 10 million rows against your WHERE clause. At even 10 ns per comparison, that's 100 ms of CPU time per query.
• And this is cold cache. If the 5 GB table fits in RAM (it probably won't), the second run is much faster.

In a real system, a full scan on a large table under production load doesn't take 1.7 seconds — it's significantly worse, because concurrent queries compete for I/O bandwidth, and the OS's page cache gets thrashed.

The conclusion is unavoidable: for any table beyond a few thousand rows, querying without an index on the filter column is not a "slow" solution — it's a broken one. The question is what structure we need to avoid the full scan.

Part 5: What We Need — The Requirements for an Index

Let's think about this as a design problem. We want a data structure that lets us answer the question "which pages contain rows where email = 'alice@example.com'?" without reading every page.

The requirements:

1. It must be sorted. If we sort rows by email, we can binary search to find the right one in O(log n) instead of scanning all n rows.

2. It must live on disk. The table has 10 million rows. The index needs to persist across restarts and survive crashes. It can't live purely in RAM.

3. It must handle writes efficiently. Rows are inserted, updated, and deleted constantly. The index must stay correct and stay sorted after every modification. A data structure that requires full re-sorting after each insert is unusable.

4. It must handle range queries. Not just WHERE email = 'x' but WHERE age > 25 AND age < 40. A structure that only supports exact matches isn't sufficient.

The obvious candidate from algorithms class is a sorted array. A sorted array of (email, page_number) pairs supports binary search — O(log n) lookups. But inserting into the middle of a sorted array requires shifting all elements after the insertion point. For 10 million rows, that's up to 10 million shifts per insert. Completely impractical for a live database.

A hash table solves the write problem — O(1) inserts and O(1) exact-match lookups. But hash tables destroy sorted order. You can't do range queries, prefix searches, or ORDER BY using a hash index. It also needs to fit in memory to be fast; a hash table scattered across disk pages is slow due to random I/O patterns.

The data structure that satisfies all four requirements is the B-Tree. It was invented in 1970 by Rudolf Bayer and Ed McCreight specifically for the problem of indexing data on disk. It is the dominant index structure in relational databases fifty years later — Postgres, MySQL, Oracle, SQL Server, SQLite all use B-Trees as their primary index structure. Understanding it from first principles will explain not just how indexes work, but why they have the specific trade-offs they have.

Part 6: The B-Tree — Built from Scratch

Start with something simpler. Imagine a binary search tree (BST). Each node holds one key and has at most two children — a left subtree where all keys are smaller, and a right subtree where all keys are larger. Searching is O(log n) for a balanced tree — each comparison eliminates half the remaining possibilities.

The BST has a fatal flaw for disk storage: it has poor fanout. Each node holds exactly one key and has at most two children. For a 10-million-row table, a balanced BST has about log₂(10,000,000) ≈ 23 levels deep. Finding a row requires traversing 23 nodes. If each node is on a different disk page (which they will be, since they're small and scattered), that's 23 random disk reads. At 100 µs each, that's 2.3 ms. Not terrible, but we can do far better.

The second flaw: BSTs become unbalanced. Insert keys in sorted order (1, 2, 3, 4, 5...) and you get a tree that degenerates into a linked list — O(n) search. Self-balancing BSTs (AVL trees, red-black trees) fix this, but they're complex and still have the low fanout problem.

The B-Tree addresses both problems with two key ideas.

Idea 1: Many keys per node. Instead of one key per node, a B-Tree node holds many keys — often hundreds. If each node holds up to 400 keys, a two-level tree can index 400 × 400 = 160,000 rows. A three-level tree can index 400³ = 64 million rows. A four-level tree: 400⁴ = 25.6 billion rows. Real Postgres tables rarely need more than 3–4 levels, regardless of table size.

Idea 2: Node size equals page size. Each B-Tree node is stored as exactly one 8KB page. Reading a node from disk is exactly one page read — the same cost as reading any other page. With 400 keys per node and 25 bytes per key-pointer pair, the math works out: 400 × 25 bytes = 10,000 bytes, well within 8KB.

The result: finding a row in a 64-million-row table requires reading exactly 3 pages. Three page reads × 100 µs per read = 300 µs total. Compare that to the 1.7-second full scan. The index makes the query roughly 5,600 times faster for this case.

The B-Tree Structure

A B-Tree has two kinds of nodes: internal nodes and leaf nodes.

                    [internal node]
                    [30 | 70 | 120]
                   /    |    |    \
          [10|20] [35|50] [80|100] [130|150|180]
          (leaves)(leaves)(leaves)   (leaves)

Internal nodes contain keys and pointers to child nodes. The keys in an internal node act as routing guides. To find the value 85, you look at the root: 85 > 70 and 85 < 120, so go down the third pointer. In that child, 85 > 80 and 85 < 100, so go down the second pointer there. You've arrived at the leaf.

Leaf nodes contain keys and pointers to the actual row data in the heap file. The pointer is a ctid — a pair of (page_number, row_offset) that tells Postgres exactly which page to fetch and where in that page the row lives.

In Postgres, the B-Tree is actually a B+Tree (the + distinguishes a specific variant). In a B+Tree:

• Internal nodes contain only keys and child pointers — no row data.
• All row data pointers live in the leaf nodes.
• Leaf nodes are connected to each other in a doubly-linked list.

The linked list of leaf nodes is crucial. It's what makes range queries efficient. To find all users with age between 25 and 40, Postgres doesn't need to traverse the tree repeatedly. It finds the leaf node containing age=25, then follows the linked list forward through leaf nodes until it passes age=40. This is a sequential scan of leaf nodes — fast.

Leaf level (linked list):
[10|20] ↔ [25|30] ↔ [35|40] ↔ [45|50] ↔ ...
   ↓         ↓         ↓         ↓
 heap      heap      heap      heap
 ctids     ctids     ctids     ctids

Inserts and the Split Operation

What happens when you insert a new key and the target leaf node is full?

The leaf node splits into two nodes, each half full, and the middle key is promoted to the parent internal node. If the parent is also full, it splits too, and promotes to its parent. In the worst case, a split propagates all the way to the root, at which point the root itself splits and the tree grows one level taller.

This is why B-Trees are self-balancing: splits and occasional root splits guarantee that all leaf nodes remain at the same depth. The tree is always balanced, always O(log n) for lookups.

The split operation requires writing 2–3 new pages to disk (the two new nodes, and the modified parent). This is why indexes make writes slower — every INSERT into a table with an index on column X requires at least one write to the B-Tree in addition to writing the heap page. For a table with 5 indexes, an INSERT writes one heap page and up to 5 B-Tree nodes. We'll explore the full trade-off in Chapter 3.

Part 7: The Buffer Pool — Your Database's RAM Cache

There's one more layer between your query and the disk that you need to understand: the buffer pool.

Postgres doesn't read pages directly from disk every time it needs them. That would be catastrophically slow — your 10-million-row users table has 655,360 pages, and if every query triggered fresh disk reads, you'd saturate your SSD within seconds under any real load.

Instead, Postgres maintains a region of RAM called the buffer pool (configured by the shared_buffers parameter). The buffer pool is a page cache: recently-read pages are kept in RAM, and subsequent reads for the same page skip the disk entirely.

The cache hit vs miss distinction maps directly back to Chapter 1's memory hierarchy. A buffer pool hit is a RAM access — sub-microsecond. A miss drops you to SSD — 100 microseconds. A 1000× difference.

The buffer pool has a fixed size. When it's full and Postgres needs to load a new page, it must evict an existing one. Postgres uses a clock sweep algorithm (a simplified variant of LRU) to decide which page to evict — roughly, it evicts pages that haven't been accessed recently.

This has a critical implication for query performance: a table that fits entirely in the buffer pool will serve all its pages from RAM after the first full scan. If your users table is 200 MB and your buffer pool is 4 GB, the entire table lives in RAM. Sequential scans become RAM scans — microseconds per page, not microseconds-from-SSD per page.

Conversely, if your table is 50 GB and your buffer pool is 4 GB, repeated full scans will constantly evict pages before they can be reused. This is cache thrashing, and it makes large table scans significantly slower than the theoretical sequential SSD throughput would suggest — because the working set doesn't fit, you end up doing a lot of random-ish I/O across a large file instead of truly sequential streaming.

The practical takeaway: shared_buffers should be set to roughly 25% of available RAM (Postgres default is only 128 MB, which is absurdly low for production). For a server with 32 GB RAM, set shared_buffers to 8 GB. Frequently accessed tables that fit within the buffer pool will be served almost entirely from RAM — effectively free in latency terms.

Part 8: Putting It Together — How Postgres Executes a Query

Let's trace through exactly what happens when Postgres executes two queries on the same table: one with a full scan, one with an index. The table: users with 10 million rows, 500 bytes per row, an index on id (primary key), no index on email.

Query A: Full scan (no index on email)

SELECT name FROM users WHERE email = 'alice@example.com';

1. Postgres's query planner estimates the cost of a sequential scan vs any available indexes. With no index on email, a sequential scan is the only option.
2. Postgres opens the heap file and begins reading pages sequentially, starting at page 0.
3. For each of the 655,360 pages, it reads the page into the buffer pool (if not already there), then checks each row on that page against the WHERE email = 'alice@example.com' condition.
4. Most pages have zero matching rows. The scan continues until either the matching row is found or all pages are exhausted.
5. The matching row is returned.

Cost: ~655,360 pages × (page read cost from disk or buffer pool). If cold: ~1.7 seconds of sequential SSD I/O. If warm in buffer pool: potentially much faster (RAM reads), but you've burned the buffer pool space to get there.

Query B: Index scan (index on id)

SELECT name FROM users WHERE id = 42;

1. The query planner sees an index on id and estimates that using it will be far cheaper than a sequential scan (because the condition is an exact match on the indexed column and the selectivity is very high — only one row will match).
2. Postgres traverses the B-Tree. The tree is 3–4 levels deep for 10 million rows.
3. Level by level, Postgres reads one internal node page per level (checking the buffer pool each time). Each node read directs it to the next level.
4. At the leaf level, Postgres finds the key id=42 and reads the ctid: say, (page 312, row offset 3). This means the row is on page 312 of the heap file, at row position 3.
5. Postgres reads heap page 312 (one page read, 8 KB), locates row offset 3, and returns the name column.

Total page reads: 3 or 4 (B-Tree traversal) + 1 (heap page) = 4–5 page reads. Cost: 4–5 × 100 µs = 400–500 µs. Under half a millisecond.

The difference — 1.7 seconds vs 0.5 milliseconds — is a factor of 3,400. That's not a performance optimisation. That's the difference between a working system and a broken one.

Part 9: Reading EXPLAIN ANALYZE

Postgres has a command that shows you exactly what execution plan it chose and how long it actually took. It's called EXPLAIN ANALYZE. You'll use this constantly when debugging slow queries in production.

Here's what the output looks like for our two queries:

Full scan output

EXPLAIN ANALYZE SELECT name FROM users WHERE email = 'alice@example.com';

Seq Scan on users  (cost=0.00..289456.00 rows=1 width=50)
                   (actual time=1721.432..1721.433 rows=1 loops=1)
  Filter: ((email)::text = 'alice@example.com'::text)
  Rows Removed by Filter: 9999999
Planning Time: 0.1 ms
Execution Time: 1721.5 ms

Seq Scan tells you it scanned the entire table. actual time=1721.432..1721.433 means it started returning rows at 1721 ms and finished at 1721 ms (only 1 row). Rows Removed by Filter: 9999999 means it looked at 10 million rows and discarded 9,999,999 of them. That's the full scan.

Index scan output

EXPLAIN ANALYZE SELECT name FROM users WHERE id = 42;

Index Scan using users_pkey on users  (cost=0.56..8.58 rows=1 width=50)
                                      (actual time=0.312..0.314 rows=1 loops=1)
  Index Cond: (id = 42)
Planning Time: 0.1 ms
Execution Time: 0.4 ms

Index Scan using users_pkey tells you it used the primary key index. actual time=0.312..0.314 — the whole thing took 0.4 ms. Zero rows removed by filter — it went directly to the right row.

Two additional fields you'll see in more detailed EXPLAIN output:

Buffers: hit=4 read=1 would mean: 4 pages came from the buffer pool (RAM hits), 1 page was read from disk. A query that shows hit=X read=0 is running entirely from RAM.

cost=0.56..8.58 is Postgres's internal cost estimate (in abstract units, not milliseconds). The planner uses these estimates to compare plans. Badly-outdated table statistics (ANALYZE keeps these fresh) can cause the planner to underestimate a full scan's cost and choose a sequential scan even when an index exists and would be faster.

Learning to read EXPLAIN ANALYZE output is one of the most practical skills in database performance work. The physical understanding from this chapter is what makes the output meaningful — you're no longer reading abstract plan nodes, you're seeing page reads.

Part 10: What This Means for How You Build

Everything in this chapter changes how you should think about your SaaS product's database.

Row size matters. Every row you insert goes into pages. Wider rows mean fewer rows per page. Fewer rows per page means more pages to scan. A table with 50-byte rows fits 163 rows per page. A table with 1,000-byte rows fits only 8 rows per page. For the same number of rows, the wider table requires 20× more pages — and 20× more I/O for a full scan. This is one reason you should avoid wide rows in heavily-queried tables: store large text blobs, JSON payloads, or rarely-accessed columns in a separate table or separate storage system.

Bloat is real. When Postgres updates a row, it doesn't modify the row in place. It writes a new version of the row and marks the old one as dead. Dead rows still occupy space in pages until VACUUM reclaims them. A heavily-updated table in a busy application can have 30–50% dead tuples by page count — meaning Postgres reads 30–50% more data than the live data size. Regular VACUUM (or autovacuum, which runs automatically) prevents this. In practice, watch your table bloat, not just table size.

The buffer pool is your most important knob. Before buying more hardware, check whether your frequently-queried tables fit in the buffer pool. If shared_buffers is set to 128 MB (the default) and your hottest table is 2 GB, you're doing constant disk I/O that could be RAM I/O with a configuration change. This is often the highest-ROI performance improvement available.

Indexes are not free. Every index you add to a table makes every INSERT, UPDATE, and DELETE on that table slower — because Postgres must maintain the index as well as the heap. A table with 10 indexes has 10 B-Trees to update on every write. We'll explore this trade-off in detail in Chapter 3. For now: don't index every column by default; index the columns you actually query on, in the ways you actually query them.

Vocabulary Map

Practice Problems

Problem 1 — Failure Analysis

Your production database is running slow. You run EXPLAIN ANALYZE on your most frequent query and see:

Seq Scan on subscriptions  (actual time=4823.1..4823.2 rows=1 loops=1)
  Filter: (user_id = 12345)
  Rows Removed by Filter: 2999999

The subscriptions table has 3 million rows. Each row is 300 bytes.

Calculate: How many pages is Postgres scanning? How long would this take if the table is cold (not in buffer pool)? How long if it's warm? The team says "just add more RAM." Is more RAM the right fix here? What's the actual fix, and why does the Seq Scan exist in the first place?

Problem 2 — Design from Scratch

You're building a multi-tenant SaaS product. You have a messages table with 500 million rows. The two most common queries are:

• SELECT * FROM messages WHERE conversation_id = X ORDER BY created_at DESC LIMIT 50 (load a conversation)
• SELECT * FROM messages WHERE user_id = X AND created_at > Y (a user's recent messages)

Design the index strategy for this table. For each index you propose: describe the physical structure (what the B-Tree is sorted by, what the leaf nodes point to), explain which query it serves, and explain what you're giving up by having it. Be specific about the write overhead — how many B-Tree pages need to be updated per INSERT?

Problem 3 — Synthesis

Connect these three concepts from this chapter: pages as the unit of I/O, the buffer pool as a RAM cache, and dead tuples from MVCC updates.

Your SaaS application updates the last_seen_at timestamp on a user row every time that user makes an API request. You have 100,000 active users, each making 20 requests per day. That's 2 million updates per day, all to rows in the users table.

Explain the chain of physical events: what happens in the buffer pool during these updates, what happens to the heap file over time, and why this specific access pattern — frequent small updates to many rows — is more damaging to database performance than inserting 2 million new rows per day. What is the right way to handle "last seen" at this scale?

Problem 4 — Go Deeper

Postgres's B+Tree leaf nodes are linked in a doubly-linked list. You now understand that this enables efficient range scans. But consider this: what happens when Postgres needs to do a range scan on a non-primary-key index, like WHERE age BETWEEN 25 AND 30?

The leaf nodes give you the ctids of matching rows. But those ctids point to rows scattered randomly across the heap file (because the heap is unordered). So after traversing the B-Tree and following the linked leaf list, Postgres must do N random heap page reads — one per matching row — rather than one sequential scan.

For what ratio of matching rows does an index scan become slower than a sequential scan? Think through the math using Chapter 1's numbers (sequential vs random I/O costs). At what selectivity threshold would a smart query planner correctly choose a sequential scan over an index scan?

(Hint: Postgres actually has logic for this — it's called a "bitmap index scan" for medium-selectivity queries. You don't need to know that term yet, but if you reason carefully through this problem, you'll understand why it exists.)

Problem 5 — Connect to Chapter 1

In Chapter 1, you made a prediction: describe what Postgres does at the memory hierarchy level when running SELECT * FROM users WHERE email = 'alice@example.com' with no index on a 10-million-row table.

Check your prediction against what you now know. Were you right about the number of layers crossed? Were you right about where the bottlenecks are? Write down specifically what you got right and what you missed — that delta is exactly what this chapter taught you.

What's Coming Next

Chapter 3 goes one step further into indexes. You now know what a B-Tree is and that it makes certain queries fast. What you don't yet know is exactly when indexes help and when they hurt — the write overhead, the cases where Postgres ignores an index you thought it would use, why the order of columns in a composite index matters enormously, and what a covering index is and why it can eliminate heap reads entirely. Chapter 3 turns the blunt tool of "add an index" into a precise instrument you can wield against any query.

Chapter 2 complete. Before moving on: do Problem 5 first — check your Chapter 1 prediction. Then work through Problems 1 and 4, which are the hardest. Problem 4 is deliberately open-ended; the goal is to think it through, not to arrive at a specific numerical answer.