S041 · Indexes — B-Tree Intuition, When to Add

Module M04: Databases & SQL · Session 41 of 130 · Track: DE 📑

What you'll be able to do after this session

• Explain Indexes to a friend in one minute, out loud, no notes.
• Recognise it when you see it in real code / systems / papers.
• Complete the hands-on exercise at the end without looking up help.

Prerequisites

If you can't answer these in 30 seconds each, redo the linked session first:

• S037 — Joins — INNER, LEFT, RIGHT, FULL, Anti-Join

Pre-read (skim before the session)

• 🎥 Intuition (5–15 min) · B-Tree Indexes — Ivan draws a B-tree from scratch on a whiteboard; simplest possible mental model.
• 🎥 Deep dive (30–60 min) · B Trees and B+ Trees. How they are useful in Databases — Abdul Bari's classic 40-minute walkthrough of how a database actually uses a B+ tree.
• 🎥 Hands-on demo (10–20 min) · Database Indexing Explained (with PostgreSQL) — Hussein Nasser types real queries and shows before/after EXPLAIN timings.
• 📖 Canonical article · PostgreSQL Docs — Index Types — B-tree, hash, GiST, GIN, BRIN — pick the right tool.
• 📖 Book chapter / tutorial · Use The Index, Luke! — Markus Winand's free book. Read chapter 1 ("Anatomy of an Index"). Life-changing.
• 📖 Engineering blog · Martin Fowler / Unmesh Joshi — Write-Ahead Log — why indexes need durable writes; connects storage → indexing.

(a) Intuition · 5 min

The one-paragraph mental model. Why this concept exists, what problem it solves, and the analogy that makes it stick.

In one sentence: The single biggest performance lever.

Imagine a 900-page cookbook with no table of contents and no index. Someone asks you: "find every recipe that uses saffron." Your only option is to open page 1 and read every single page to the end. That's a full table scan — what a database does when there's no index. On a table with 200 million rows, that's coffee-break territory: minutes, sometimes hours.

Now imagine the same book with an alphabetical index at the back: "saffron … pages 47, 213, 588." You flip to the index (which itself is sorted, so you binary-search it in seconds), grab the three page numbers, and jump directly. That's exactly what a database index does. Under the hood, most relational databases (Postgres, MySQL/InnoDB, SQL Server, Oracle) use a B-tree — a shallow, wide, self-balancing tree — so that even for a billion-row table, finding a specific value takes ~4 disk reads instead of 4 billion.

The catch, and the gotcha you must carry forever: every index you add makes writes slower and takes disk space. When you INSERT a row into a table with 5 indexes, the database has to update 5 trees, not one. Indexes are not free lunches — they trade write speed and storage for read speed. The mantra is: add indexes for queries that run often and hurt; do not add "just in case."

(b) Visual walkthrough · 15 min

Diagrams, worked examples, step-by-step visuals.

A B-tree is a wide, shallow tree where each node holds many keys in sorted order. Here is a tiny B-tree indexing 15 rows on the column user_id:

Worked example — lookup user_id = 50:

1. Read root. 50 falls between 40 and 60, so descend into node C.
2. Read node C. 50 matches; follow the pointer to the actual row on disk.
3. Done — 2 reads, not 15.

Now blow this up to a real table: with a branching factor of ~200 per node, a B-tree over 1 billion rows is only about 4 levels deep. Every lookup is ~4 page reads, regardless of table size. That is the magic.

When indexes help vs. hurt:

Rule of thumb (selectivity): an index is useful when it filters out roughly 95% or more of rows. If you're returning half the table, a scan is often faster because random I/O for millions of tuple pointers is slower than one big sequential read.

(c) Hands-on · 20 min

Code you type and run. Not pseudo-code — real, runnable, copy-pasteable.

Spin up Postgres locally (Docker), load 1M rows, and watch the difference an index makes.

# 1. Start Postgres in one line
docker run --rm -d --name pg-lab -e POSTGRES_PASSWORD=pw -p 5432:5432 postgres:16
sleep 3
psql "postgres://postgres:pw@localhost:5432/postgres" <<'SQL'
-- 2. Create a table and stuff it with 1M rows
CREATE TABLE users (
    id          bigserial PRIMARY KEY,
    email       text NOT NULL,
    country     text NOT NULL,
    created_at  timestamptz NOT NULL DEFAULT now()
);
INSERT INTO users (email, country)
SELECT
    'user_' || g || '@example.com',
    (ARRAY['US','IN','DE','JP','BR'])[1 + (g % 5)]
FROM generate_series(1, 1000000) g;
 
-- 3. Query WITHOUT index — full scan
EXPLAIN ANALYZE
SELECT * FROM users WHERE email = 'user_987654@example.com';
-- Note the "Seq Scan" and the execution time (~150-400 ms).
 
-- 4. Add a B-tree index
CREATE INDEX idx_users_email ON users(email);
 
-- 5. Same query WITH index
EXPLAIN ANALYZE
SELECT * FROM users WHERE email = 'user_987654@example.com';
-- Now "Index Scan", ~0.1-0.5 ms. A 1000x speedup.
 
-- 6. Show that low-selectivity queries STILL do a seq scan
EXPLAIN ANALYZE
SELECT count(*) FROM users WHERE country = 'US';
-- Planner ignores an index on `country` even if you add one — it's cheaper to just scan.
 
-- 7. Index size (indexes are NOT free)
SELECT pg_size_pretty(pg_relation_size('idx_users_email')) AS index_size,
       pg_size_pretty(pg_relation_size('users'))          AS table_size;
SQL
 
# When done:
docker stop pg-lab

Observe (checklist):

1. Look for Seq Scan vs Index Scan in the EXPLAIN output — this is the smoking gun.
2. Compare execution time before vs after the index — expect 100–1000x.
3. Notice the index takes ~30–50 MB — real cost.
4. Confirm the planner refuses to use the index for country = 'US' — high selectivity matters.
5. Try WHERE email LIKE '%example.com' and confirm it seq-scans (leading wildcard defeats B-tree).

Try this modification: add a composite index CREATE INDEX ON users(country, created_at) and run EXPLAIN ANALYZE SELECT * FROM users WHERE country='US' ORDER BY created_at DESC LIMIT 10; — does the planner use the index now? Why does column order matter?

(d) Production reality · 10 min

How this shows up in real systems, gotchas, war stories, common bugs.

The single most common outage story you'll hear from database people: an index was added on a hot table during peak traffic, and it took an exclusive lock on the table for 20 minutes. In Postgres the fix is CREATE INDEX CONCURRENTLY — takes 3x longer, but doesn't block writes. Every senior engineer has learned this the hard way. Second most common story: CREATE INDEX CONCURRENTLY failed halfway through and left an INVALID index that silently returns wrong results. Always check pg_indexes for invalid indexes after a concurrent build.

At Microsoft, Amazon, and every FAANG-scale shop, index review is part of code review — no schema PR ships without justifying every new index. Uber famously wrote about how MySQL's clustered index (rows physically ordered by PK) forced their PK design choices. Instagram wrote about how a single missing composite index on (user_id, created_at) caused a 4-hour Feed outage in 2018.

The other trap: over-indexing. A table with 20 indexes will have insert throughput cut by 10-20x versus the same table with 3 indexes. Airbnb's data platform team ran an audit in 2021 that found ~40% of their production indexes were never used by any query — pure write tax. Tools like pg_stat_user_indexes (Postgres) and sys.dm_db_index_usage_stats (SQL Server) let you find and drop them.

Finally: primary keys and foreign keys are not automatically indexed the same way. PK is always indexed. But in Postgres, foreign key columns are NOT auto-indexed — you have to add them yourself, and forgetting causes catastrophic slowdowns when you delete a parent row (each delete triggers a seq scan on every child table). Add CREATE INDEX ON child_table(parent_id) for every FK. Every time.

(e) Quiz + exercise · 10 min

1. In one sentence, why is a B-tree index O(log n) instead of O(n)?
2. Name three query patterns that make an index useless even if it exists.
3. What does "selectivity" mean, and roughly what selectivity do you need before an index is worth using?
4. Why does adding an index slow down INSERTs?
5. What is the difference between CREATE INDEX and CREATE INDEX CONCURRENTLY in Postgres, and when would you always prefer the latter?

Stretch (connects to S037 — SQL Joins): you have orders (id, customer_id, created_at) and customers (id, country). A query SELECT * FROM orders o JOIN customers c ON c.id = o.customer_id WHERE c.country = 'DE' AND o.created_at > now() - interval '7 days' is slow. Which indexes would you add, on which tables, and in which column order — and why does the join order the planner picks matter?

Explain-out-loud test

If you can't teach these 3 things to a friend without notes, redo the session:

1. What is Indexes? (one sentence, no jargon)
2. When would you use it? (one concrete example)
3. When would you NOT use it? (one anti-pattern)

What comes next

• Next session (S042): Transactions & ACID — Isolation Levels, MVCC
• Previous (S040): CTEs & Recursive Queries
• Hub: The 6-Month Learning Plan

Part of a 130-session evergreen learning series. Session structure: (a) intuition · (b) visual walkthrough · (c) hands-on · (d) production reality · (e) quiz + exercise. Duration: 60 minutes.