Understanding SQL Indexes and Query Performance

Part 3 of 16 · ~4 min

How a B-Tree Index Is Organized

We have an index on dept. Before we build any more, it is worth knowing what is actually inside one, because every rule in the rest of this reference is a consequence of that structure rather than an arbitrary convention.

Start concretely. Here is what idx_emp_dept literally contains for the code lab's five rows — not a metaphor, the actual entries:

'HR'    → row 5   (Eve)
'IT'    → row 3   (Carol)
'IT'    → row 4   (Dave)
'Sales' → row 1   (Alice)
'Sales' → row 2   (Bob)

Two observations, and they are the two that matter. The entries are sorted by dept, not by id — the index imposes its own order, which is the whole reason it can narrow a search. And each entry carries a pointer back to the row, because the index holds dept and nothing else; if you want Alice's salary, the index cannot give it to you.

At five rows that list fits on one page and the story ends there. At 2.4 million rows it does not, and the structure that results is a B-tree — specifically a B+tree in most engines, and it's the structure Postgres, MySQL's InnoDB, SQL Server, and SQLite all reach for without you asking. It is a tree of pages, arranged so that:

• Leaf nodes hold the actual sorted entries — the five lines above, spread across thousands of pages. For a non-clustered index each entry is a value plus a row pointer; for a clustered index the leaf entry is the whole row, which is the next chapter's subject.
• Internal nodes hold routing keys rather than data. An internal node says something like "everything below this pointer starts with a value less than 'IT'; everything below the next one is 'IT' or greater." Their only job is to steer a descent toward the right leaf.
• The tree is balanced, meaning every leaf sits the same number of levels below the root. This is what makes the guarantee uniform: looking up 'Facilities' and looking up 'Sales' cost the same number of page reads, because both are the same distance down. A tree that could go lopsided would make some lookups fast and others accidentally terrible.

The depth stays small in a way that is genuinely surprising the first time you work it out. Each internal node holds hundreds of routing keys, so the branching factor is in the hundreds rather than two. Three levels of that covers millions of rows comfortably. Finding one employee among 2.4 million is a handful of page reads, and that is the number that turned four seconds into eight milliseconds.

Then there is the property that does not get enough attention, and that we are going to lean on heavily from chapter 5 onward:

Because the leaves are sorted and linked to their neighbours, a B-tree answers range queries as efficiently as exact matches. The pay-band screen needs salary BETWEEN 60000 AND 90000. On a B-tree, that is not "find 60000, find 60001, find 60002" — it is one descent to the first entry at or above 60000, and then a straight walk sideways along the leaves until the values pass 90000. One seek plus a sequential read. The same mechanism handles >, <, BETWEEN, and ORDER BY, all for the same reason: the data is already in order.

That property is exactly what a hash index gives up. A hash index scatters values by their hash, which makes exact matches theoretically quicker and makes ranges impossible — salary > 60000 has no meaning in a structure where 60000 and 60001 land in unrelated buckets. Some engines offer one; it is rarely the default, and reaching for it means committing that a workload is exact-match-only forever. For the pay-band screen it would be actively wrong, because half the query is a range.

Last piece, and it is the one the bill in chapter 12 is written against: the tree maintains its own balance. Insert enough rows into one leaf and it fills up, so the engine splits it in two and pushes a new routing key up into the parent — which may itself fill and split. Delete enough and pages get merged or left partly empty. All of that bookkeeping happens on writes, not reads. When we get to why the raise run got slower, this paragraph is the reason.