Chapter 73·Intermediate·10 min read
How Indexes Work: Inside the B-Tree
A deep, plain-English explanation of database indexes — why a full table scan is slow, how a B-tree turns lookups from linear to logarithmic, what a composite index really orders, and when an index hurts instead of helps.
July 2, 2026
In the previous chapter we built well-typed tables. Now the practical question: given a table with ten million rows, how does WHERE email = 'ada@example.com' return in a millisecond instead of a second? The answer is the index, and understanding it deeply separates engineers who guess at performance from those who reason about it.
The problem: the full table scan
Without help, finding matching rows means checking every row — a full table scan. For a hundred rows it's instant. For ten million it's a disaster: the work grows linearly with the table, so the query gets slower every month as data accumulates.
That gap — ten million reads versus four — is the entire reason indexes exist. An index is a separate, sorted structure that lets the database navigate straight to the rows it wants.
Why sorted data is fast: logarithmic lookup
Sorting unlocks a trick you already know: to find a name in a physical dictionary, you don't read from page one. You open the middle, decide which half holds your word, and repeat. Each step halves what's left. That's binary search, and its cost grows logarithmically — doubling the data adds just one step.
Twenty-three steps to search ten million rows. That's the shape of every index lookup, and it's why an index feels like magic: the table can grow enormously while queries barely slow down.
The B-tree: binary search that lives on disk
Real databases can't hold everything in memory or search a flat sorted array efficiently on disk, so they use a B-tree (more precisely, a B+tree). Picture a shallow tree of sorted keys:
- The root and branch nodes hold ranges — signposts saying "keys 1–1000 that way, 1001–2000 this way."
- The leaf nodes hold the actual keys in sorted order, each pointing to its row.
Because each node holds hundreds of keys, the tree stays wide and shallow — usually three or four levels deep even for billions of rows. A lookup reads the root, follows one pointer per level, and lands on the leaf: a handful of disk reads regardless of table size. And because the tree rebalances on every insert, it never degrades into a slow, lopsided shape.
Composite indexes and the leftmost-prefix rule
You can index multiple columns together — a composite index on (user_id, created_at). Crucially, it sorts by user_id first, then created_at within each user. That ordering decides what it can accelerate:
WHERE user_id = 1— fast (uses the leading column).WHERE user_id = 1 AND created_at > '2026-01-01'— fast (uses both, in order).WHERE created_at > '2026-01-01'— cannot use this index efficiently;created_atis only sorted inside each user, not globally.
This is the leftmost-prefix rule: a composite index helps queries that use a prefix of its columns, left to right. Getting the column order right — most-selective and most-filtered-on first — is one of the highest-leverage decisions in database performance.
Covering indexes: skip the table entirely
Normally an index gets you to the row, then the database reads the row for the columns you actually selected. But if the index already contains every column the query needs, that second step vanishes — a covering index. The query is answered from the index alone, never touching the table. For hot read paths, this is the fastest tier available.
The cost: writes pay for every index
Indexes are not free, and this is where over-indexing bites. Every index is a second structure that must stay in sync, so every insert, update, and delete must update every relevant index. Ten indexes means a write does roughly ten times the index maintenance.
So the discipline is: index the columns you filter, join, and sort by — and no more. A missing index on a hot query is the classic cause of a slow database; a pile of unused indexes is the classic cause of slow writes and wasted storage.
Recap
- A full table scan reads every row — linear cost that worsens as the table grows.
- An index is a sorted structure enabling logarithmic lookup: doubling the data adds one step, not double the work.
- Databases use a B-tree — wide, shallow, self-balancing — so lookups take a handful of disk reads at any scale.
- A composite index sorts left-to-right; it helps queries using a leftmost prefix of its columns, so column order matters.
- A covering index answers a query without touching the table at all.
- Every index is paid for on writes — index deliberately, not exhaustively.
Indexes get us to rows fast. Next we follow the links between tables — and see how the database decides how to run a query. Continue to Joins & Query Planning.