Day 38 · The index at the back of the book

Database Internals

You will be able to

Explain why databases use B-trees rather than binary trees or hash maps
Read EXPLAIN QUERY PLAN output and tell a scan from an index search
Create the right index for a query and measure the speedup
Demonstrate a transaction's atomicity with a deliberate mid-way failure
Recognize and fix the N+1 query problem

Today's ~120 minutes

Spaced-rep warm-up: due cards (joins, BSTs, binary search)	10 min
ELI5 + tech read; trace a key descent in the B-tree visualizer	18 min
Guided: index physics + atomic money + N+1 hunt	42 min
Practice: slow-query clinic	20 min
Project: index audit of the tracker schema	20 min
Quiz + flashcards	10 min

Builds on: Day 37 — SQL II — joins & modeling · Day 29 — Binary trees & BSTs · Day 33 — Binary search

The analogy

🧸 ELI5⚙ Tech

Find every mention of "entropy" in a 600-page textbook. Plan A: read all 600 pages — a full scan. Plan B: flip to the index at the back, which says "entropy: pages 214, 388" — three seconds. The index is a separate, alphabetically sorted mini-book of "term → where to find it," maintained precisely so you never have to read everything.

A database index is exactly that, with one twist driven by physics. Disks hand data over in big pages, not single words, so the index is built as a B-tree: like Day 29's search tree, but each node is a page holding HUNDREDS of sorted keys with hundreds of children. Hundreds of branches per step means a billion rows sit only three or four page-reads from the root — a binary tree would need thirty.

The catch is the same as a book index: every edit to the book means updating the index too. Write a row, update every index on that table. Indexes are a tax on writes to subsidize reads, and choosing WHICH columns deserve one is the craft. The other star today: transactions. Move money between accounts and crash halfway — the database promises all-or-nothing, so the half-finished transfer simply never happened.

Why this matters on the job

"The app is slow" is, in an enormous fraction of real incidents, "a query is scanning instead of seeking" — and the fix is a one-line CREATE INDEX found by reading a query plan, one of the highest-leverage skills an engineer carries on-site. The N+1 problem is its evil twin: ORMs generate it silently, and you will diagnose it in customer codebases as an FDE. Transactions are why your Day 42 service can crash mid-write without corrupting data. And this whole toolbox transfers upward: Day 115's vector indexes make the same read-vs-write, exact-vs-fast trade-offs, and interviewers love "why B-trees and not hash maps?" as a systems probe.

Watch it happen

The index at the back of the book — scan vs B-tree descent

step 1 / 6

Query: WHERE id = 61. Without an index the database FULL-SCANS: reads every disk page and checks every row. Watch the cost mount.pages read: 3 and counting…

🎯 Predict modespeed1×

Guided practice

guided 1

Watch an index change the physics

22 min

Create internals_lab.py. The starter builds a 200,000-row events table with random user_ids and timestamps. Run it (a few seconds).
Time the query "events for user 4242" and read its plan: EXPLAIN QUERY PLAN says SCAN events — the 600-page read.
Create the index on user_id. Re-run the SAME query: plan now says SEARCH events USING INDEX, and the timing drops by orders of magnitude. Record both numbers — this before/after is the most persuasive demo in databases.
Check the fine print: run a query filtering on kind (unindexed) — still a SCAN; the index on user_id is irrelevant. Then ORDER BY user_id LIMIT 10 — the index serves ordering too. Explain both from the sorted-B-tree picture.
Measure the write tax: time inserting 20,000 more rows with the index present vs after DROP INDEX (starter has both paths). Writes pay for reads — say the trade out loud.

🐍 python — editable, runs in your browser

import random, sqlite3, time

conn = sqlite3.connect(":memory:")
conn.execute("""
    CREATE TABLE events (
        id      INTEGER PRIMARY KEY,
        user_id INTEGER NOT NULL,
        kind    TEXT NOT NULL,
        ts      TEXT NOT NULL
    )
""")
kinds = ["view", "click", "purchase"]
rows = [(random.randint(1, 20_000), random.choice(kinds),
         f"2026-{random.randint(1,12):02d}-{random.randint(1,28):02d}")
        for _ in range(200_000)]
conn.executemany("INSERT INTO events (user_id, kind, ts) VALUES (?, ?, ?)", rows)
conn.commit()

def timed(label, sql, params=()):
    t0 = time.perf_counter()
    n = len(conn.execute(sql, params).fetchall())
    ms = (time.perf_counter() - t0) * 1000
    plan = conn.execute("EXPLAIN QUERY PLAN " + sql, params).fetchall()
    print(f"{label:28s} {n:5d} rows  {ms:8.2f} ms   plan: {plan[0][3]}")

timed("no index", "SELECT * FROM events WHERE user_id = 4242")

conn.execute("CREATE INDEX idx_events_user ON events(user_id)")
timed("with index", "SELECT * FROM events WHERE user_id = 4242")
timed("unindexed column", "SELECT * FROM events WHERE kind = 'purchase'")
timed("order-by uses index", "SELECT * FROM events ORDER BY user_id LIMIT 10")

more = [(1, "view", "2026-09-01")] * 20_000
t0 = time.perf_counter()
conn.executemany("INSERT INTO events (user_id, kind, ts) VALUES (?, ?, ?)", more)
print(f"insert 20k WITH index:    {(time.perf_counter() - t0) * 1000:8.1f} ms")
conn.execute("DROP INDEX idx_events_user")
t0 = time.perf_counter()
conn.executemany("INSERT INTO events (user_id, kind, ts) VALUES (?, ?, ?)", more)
print(f"insert 20k WITHOUT index: {(time.perf_counter() - t0) * 1000:8.1f} ms")

Ctrl/⌘+Enter runs · Tab indents · numpy/pandas/sklearn auto-load on import (torch and network calls need a local run)

guided 2

Atomic money + hunting the N+1

20 min

Add the accounts table (starter) with two accounts of 100 each and a CHECK (balance >= 0). Write transfer(a, b, amount) as two UPDATEs inside with conn:.
Transfer 150 — more than Amara has. The second UPDATE violates the CHECK, the exception fires, and with conn: rolls back BOTH updates: print balances and verify no money was created or destroyed. Now comment out the transaction (autocommit each UPDATE separately) and repeat — money vanishes. Restore the transaction and never speak of it again.
The N+1 hunt. The starter fetches 200 recent events, then loops fetching each event's user row — 201 queries. Time it.
Rewrite as ONE join query. Time it. On an in-process engine the gap is real but modest; say why it becomes catastrophic when each query crosses a network to Postgres (~1ms round trip × N).
Count queries with the starter's counter wrapper to prove it: 201 vs 1. That counter trick — logging actual query counts — is exactly how you will catch ORMs doing this behind your back.

🐍 python — editable, runs in your browser

conn.execute("""
    CREATE TABLE accounts (
        id      INTEGER PRIMARY KEY,
        name    TEXT NOT NULL,
        balance REAL NOT NULL CHECK (balance >= 0)
    )
""")
conn.execute("INSERT INTO accounts (id, name, balance) VALUES (1, 'Amara', 100), (2, 'Bo', 100)")
conn.commit()

def balances():
    return conn.execute("SELECT name, balance FROM accounts ORDER BY id").fetchall()

def transfer(frm, to, amount):
    with conn:                                # BEGIN; commit on success, rollback on error
        conn.execute("UPDATE accounts SET balance = balance - ? WHERE id = ?", (amount, frm))
        conn.execute("UPDATE accounts SET balance = balance + ? WHERE id = ?", (amount, to))

print("before:", balances())
try:
    transfer(1, 2, 150)                       # Amara only has 100 -> CHECK fails
except sqlite3.IntegrityError as e:
    print("rolled back:", e)
print("after: ", balances())                  # both balances unchanged

# ---- the N+1 problem ----
import time
t0 = time.perf_counter()
events = conn.execute("SELECT id, user_id FROM events LIMIT 200").fetchall()
for _id, uid in events:                       # 200 extra queries...
    conn.execute("SELECT COUNT(*) FROM events WHERE user_id = ?", (uid,)).fetchone()
print(f"N+1 style:  {(time.perf_counter() - t0) * 1000:7.1f} ms  (201 queries)")

t0 = time.perf_counter()
conn.execute("""
    SELECT e.id, e.user_id, u.n
    FROM (SELECT id, user_id FROM events LIMIT 200) e
    JOIN (SELECT user_id, COUNT(*) AS n FROM events GROUP BY user_id) u
      ON u.user_id = e.user_id
""").fetchall()
print(f"one query:  {(time.perf_counter() - t0) * 1000:7.1f} ms  (1 query)")

Ctrl/⌘+Enter runs · Tab indents · numpy/pandas/sklearn auto-load on import (torch and network calls need a local run)

On your own

The slow-query clinic, database edition

20 min

Three "production complaints" against your 200k-row events table. For each: read the plan, diagnose, fix, prove with before/after timings. (1) "The activity page is slow": SELECT * FROM events WHERE user_id = ? AND kind = 'purchase' — a single-column index exists on user_id; would a composite (user_id, kind) beat it, and does column order matter? Test both orders. (2) "The export is slow": SELECT user_id, ts FROM events WHERE user_id = ? — make the query covering so the plan says the table is never touched (add ts to the index) and find the plan's covering-index marker. (3) "Inserts got slow after we added five indexes": drop to the minimum set that keeps queries 1–2 fast, and defend your choice in two sentences.

Hints: EXPLAIN QUERY PLAN before and after every change; (user_id, kind) serves user_id-only queries too, so it can REPLACE the single-column index.

Ship before you stop

Index audit of your tracker schema

Return to yesterday's task-tracker schema with today's eyes. In tracker_audit.py: (1) seed it up to ~50,000 tasks with realistic skew (a few users own most tasks); (2) take your five Day 37 product queries, EXPLAIN each, and record which ones SCAN; (3) design and create the minimal index set that turns every hot query into a SEARCH — with the reasoning for each index (and each index you deliberately did NOT add) as comments; (4) demonstrate one transaction: "complete task and log the completion" as an atomic pair with a forced failure showing rollback; (5) record before/after timings in the docstring. Commit — the Day 42 service inherits this schema and its indexes.

Rubric — check what you completed (0/5)

All five queries EXPLAINed with plans recorded before and after indexingEvery hot query shows SEARCH (or covering index) in its final planAt least one candidate index rejected in comments with a write-cost justificationAtomic complete-and-log demonstrated with a forced rollback keeping data consistentBefore/after timings in the docstring; committed to the practice repo

Common mistakes & misconceptions

Indexing every column "to be safe." Each index taxes every INSERT/UPDATE and bloats the file; index the columns your actual queries filter, join, and sort on.
Expecting an index on (a, b) to speed queries filtering only on b. Composite indexes sort by the FIRST column; b-only queries scan. Order composites by how you query.
Believing a hash map would beat a B-tree for a database index. Hashes cannot do ranges, prefixes, or ORDER BY — the questions databases live on.
Writing multi-statement changes without a transaction. A crash between the UPDATEs leaves half-transferred money; with conn: makes it all-or-nothing.
Diagnosing slowness by staring at code instead of running EXPLAIN. The plan tells you scan-vs-search in one line; guessing tells you nothing.
Shipping an ORM loop that queries per row (N+1) because each line "looks innocent." Count actual queries; fetch related rows in one JOIN or IN.

Knowledge check

Q1. Why do databases build indexes as B-trees with huge nodes instead of binary search trees?

Q2. EXPLAIN QUERY PLAN shows "SCAN orders" for WHERE customer_id = 7, and the query is slow. Best next move?

Q3. A crash occurs after "debit A" but before "credit B". With both UPDATEs in one transaction, what happens on restart?

Go deeper — curated resources

bookUse The Index, Luke — Anatomy of an Index ↗30 min docsSQLite — The Query Planner (official) ↗20 min courseCMU 15-445 — Database Systems (index lectures for the third hour) ↗20 min

If you have a third hour

Isolation levels, concretely — Look up read-uncommitted through serializable and the anomalies each allows (dirty read, non-repeatable read, phantom). Postgres defaults to READ COMMITTED — connect that to why Day 46 cares about concurrent writers.

Done means

Before/after index timings recorded with matching plan changes
Write-tax measurement done and the trade-off stated
Rollback demo leaves balances consistent; N+1 fixed and query-counted
Index audit committed with reasoning for every index kept and rejected
Quiz ≥ 2/3

How this connects

← Back: The B-tree is Day 29's search tree re-engineered for Day 33's halving at page scale; the queries being accelerated are Day 36–37's. The timing-first discipline is Day 22's lab, pointed at storage.

Forward →: Day 42's service inherits this schema, its indexes, and EXPLAIN as its debugging tool. Day 47 adds caching in front of the database, Day 115's vector indexes rerun the same read/write trade-offs for embeddings, and Day 118 joins SQL filters with semantic search.

Unlocks: D42 Week 6 Checkpoint: API + DB Mini-Service · D44 Security, AuthN & AuthZ · D46 Distributed Systems Fundamentals · D48 System Design Method