B-tree indexes: how a lookup really works

Last lesson ended on a smell: a query read 1091 pages to return 94 rows, throwing away 119,906 along the way. That's a sequential scan — Postgres read the entire heap because it had no faster way to find those 94 rows. You already know the fix is "add an index," the way you know useMemo makes React faster: true, but useless until you know what it actually builds. An index is not a vague speed boost. It's a concrete on-disk data structure — almost always a B-tree — and once you can picture the tree, you can predict exactly when it helps, when the planner ignores it, and why every index you add makes writes slower.

The problem, stated precisely

You want one row (or a small range of rows) out of a million, keyed on some column, without reading a million rows. A sequential scan is O(n) in pages — fine for 1000 rows, ruinous for 100 million. What you want is something closer to how you find a word in a physical dictionary: you don't read every page; you open to the middle, see you've gone too far, jump back, and converge in a handful of steps. That's a tree search, and it's O(log n). The whole job of a B-tree index is to be that dictionary — a sorted structure you can binary-search from the top instead of scanning from the front.

What a B-tree actually is

The "B-tree" Postgres builds is, in practice, a B+ tree, and two properties of it matter more than the name:

1. All the actual keys-plus-pointers-to-rows live in the leaf level. The internal (upper) levels hold only separator keys — signposts that say "keys less than X are down this branch, keys ≥ X are down that one." You never find your answer in an internal node; you use internal nodes only to navigate down to the correct leaf.
2. The leaves are linked to their siblings in sorted order, like a doubly-linked list. Once a lookup lands on the right leaf, a range query (created_at BETWEEN … AND …, ORDER BY … LIMIT) can just walk sideways leaf-to-leaf without ever going back up the tree.

Each node of the tree is — of course — an 8KB page, the same unit as everything in the last lesson. And here's the number that makes B-trees feel like magic: because each key is small (an integer, a ULID, a short string) and a page is 8KB, hundreds of keys fit in a single node. That's the tree's fan-out — how many children each node points to. With a fan-out of, say, a few hundred, the arithmetic is startling:

level 0 (root):        1 page,      ~hundreds of separator keys
level 1 (internal):    ~hundreds of pages
level 2 (internal):    ~hundreds²  of pages
level 3 (leaves):      ~hundreds³  of pages  →  billions of keys

fan-out 300:  300³ ≈ 27 million,  300⁴ ≈ 8 billion keys

A tree only 3 to 4 levels deep indexes a table with billions of rows. That is the whole payoff: any single row is reachable in 3–4 page reads instead of a million. And the top levels are so small and so frequently touched that they live permanently in the buffer pool — so in practice only the last hop or two ever touches disk.

                 [ root page ]
                 | k<M | k≥M |
                /           \
      [ internal ]          [ internal ]
      | .. | .. |           | .. | .. |
       /       \             /       \
   [leaf]→→→[leaf]→→→→→→[leaf]→→→[leaf]      ← siblings linked, sorted
     |        |            |        |
   (TID)    (TID)        (TID)    (TID)      ← each leaf entry points into the heap

One lookup, step by step

Say you run SELECT * FROM messages WHERE id = '01H8X…' with a B-tree index on id. Here's every hop:

1. Read the root page. Binary-search its separator keys to decide which child branch '01H8X…' falls into. Follow that pointer. (Root is almost always a buffer-pool hit.)
2. Read the internal page you were sent to. Binary-search its separators, pick the next branch down.
3. Read the leaf page. Binary-search it to find the exact index entry for '01H8X…'. That entry contains the key and a TID — remember from D1, the (page number, slot number) address of the actual row in the heap.
4. Heap fetch. Now go read that heap page and pull the tuple at that slot.

Steps 1–3 walked the index; step 4 went to the table itself. And here's the part people miss: step 4 is usually the expensive one. The index pages are few, hot, sorted, and cached. The heap page could be anywhere — and if your query matches many rows scattered across the table, each match is a separate random heap fetch to a different page. Recall the sequential-vs-random asymmetry from D1: an index turns one big sequential scan into many small random reads. That's a fantastic trade when you're fetching a handful of rows, and a terrible one when you're fetching a third of the table — which is the seed of "why the planner ignored my index," below.

Composite indexes and the leftmost-prefix rule

You can index more than one column: CREATE INDEX ON messages (group_id, created_at). This does not build two indexes. It builds one tree whose keys are the pair (group_id, created_at), sorted first by group_id, and then by created_at within each group_id — exactly like a phone book sorted by last name, then first name.

That sort order is everything, and it gives the leftmost-prefix rule: an index on (A, B) can efficiently serve a query that filters on A, or on A AND B, but not a query that filters only on B. Ask the phone book for everyone named "Priya" (any last name) and its last-name-first ordering is useless — Priyas are scattered across every letter. Same tree, same data, but the query has to match a prefix of the sort key or the tree can't narrow the search.

That third row is a quiet superpower: because the leaves are physically sorted by created_at within a group_id and linked to their siblings, WHERE group_id = X ORDER BY created_at LIMIT 50 doesn't sort anything at all — it finds the start leaf and walks sideways 50 entries. This is why the column order in a composite index is a real design decision, not a formality: put the column you filter for equality first, the column you range-scan or sort by second.

Index-only scans (and a catch to remember)

Sometimes you can skip the expensive heap fetch entirely. If an index contains every column the query needs, Postgres can answer straight from the leaf entries and never touch the heap — an index-only scan. An index on (group_id, created_at) serving SELECT created_at FROM messages WHERE group_id = X needs nothing the index doesn't already hold. Postgres also lets you bolt extra payload columns onto an index purely for this purpose: CREATE INDEX … (group_id) INCLUDE (created_at) — a covering index, carrying columns it doesn't sort by, just so lookups don't have to visit the table.

But there's a catch that ties straight back to D1's hidden tuple header, and forward to D4: the index entry does not record whether a row version is still visible to your transaction — that lives in the heap tuple's xmin/xmax. So Postgres keeps a visibility map marking which heap pages are "all-visible" (every row on them is visible to everyone). An index-only scan works only for pages the visibility map has flagged clean; for the rest it must fall back and visit the heap after all. A table that's just been heavily updated has a stale visibility map, so your index-only scan quietly does heap fetches anyway until VACUUM catches up. File that away — it's a thread we pick up in the MVCC lesson.

When the planner ignores your index

The most confusing moment in database work is adding the perfect index and watching EXPLAIN do a sequential scan anyway. Usually the planner is right. The common reasons:

• Low selectivity. If your WHERE matches a large fraction of the table (say a boolean is_active = true that's true for 80% of rows), the index would mean thousands of random heap fetches — and a sequential scan of the whole table is cheaper. Indexes win when they exclude most of the table; they lose when they don't. This is the random-vs-sequential trade-off from D1 making a decision.
• A function wraps the column. An index on created_at sorts by created_at, not by date(created_at). So WHERE date(created_at) = '2026-07-09' can't use it — the tree isn't sorted the way the expression asks. (The fix is an expression index on date(created_at), which builds a tree sorted that way.)
• A type mismatch. Compare a bigint column to a numeric value — WHERE id = 12345.0, or a driver that binds your parameter as numeric — and Postgres resolves it as numeric = numeric, which casts the column side to make the comparison. That wraps the column in a cast and defeats the index for exactly the same reason as the function case above. (Postgres won't silently coerce across unrelated types like text vs integer — that comparison just errors — but within the numeric family the quiet cast is real, and drivers do it to you.)
• Stale statistics. The planner chooses using sampled statistics about how many rows a filter will match. If those are stale (a big data change with no ANALYZE), it can badly misjudge selectivity and pick the wrong plan. ANALYZE refreshes them.

The tool for all of these is the same one from D1: EXPLAIN (ANALYZE, BUFFERS). It tells you the plan the planner chose and the rows it actually matched, so you can see whether it skipped your index because it was smart or because the query defeated the index.