How do database indexes work? B-trees, page by page

Somewhere in your codebase there is a query that returns one row and reads ten million to find it. Nobody planned that. The table was small when the query was written, the test database is still small, and the production table grew a few thousand rows a day until "instant" quietly became 900 milliseconds. The fix is usually one line of SQL. Understanding why that line works, and why it sometimes does nothing at all, is the part that pays rent for the rest of your career.

The core idea fits in a sentence: an index is a small sorted structure that lets the database skip reading almost everything. The rest of this article is what "small", "sorted", and "almost everything" mean at the level of actual pages on disk, and why the query planner sometimes refuses an index you carefully created.

What an index actually is

A table's rows live in pages: fixed-size blocks, 8 KB each in PostgreSQL, filled in whatever order rows happened to arrive. When you ask for the one row where reference = 'KB-2049-1177' and the database has nothing better to go on, it does the only honest thing available. It reads every page and checks every row. That is a sequential scan, and its cost scales with the size of the table rather than the size of the answer.

An index is a second, separate structure that stores just the indexed column's values in sorted order, each with a pointer back to the row it came from. Sorted data changes the game, because sorted data can be searched by repeated halving instead of full inspection. Ten million unsorted rows can demand ten million comparisons; ten million sorted values need about 23.

Databases do not keep a flat sorted array, though, because inserting into the middle of a flat array means shoving everything after it. They use a B-tree: the sorted values grouped into pages at the bottom, with a small tree of guide pages above them whose entries say, in effect, "keys before 'KB-31' live down there on the left." Every level is itself sorted, so the same repeated-halving trick works page by page.

Why three levels reach ten million rows

Sequential scan

10,000,000

rows touched

912 ms reads the table

Index lookup

3

pages touched

0.06 ms reads the tree

The property that makes B-trees absurdly effective is fanout. An 8 KB index page does not hold two child pointers like the binary trees from your data structures course. It holds hundreds of entries. A root page pointing at hundreds of internal pages, each pointing at hundreds of leaf pages, each holding hundreds of sorted keys, multiplies out to tens of millions of entries in just three levels. A fourth level reaches billions.

A lookup starts at the root, follows one pointer down to an internal page, follows one more to a leaf, and finds the key there along with the row's address. Three index pages, plus one table page to fetch the row itself. Four 8 KB pages, roughly 32 KB of reading, against a 10-million-row table that occupies about 100,000 pages and 800 MB. The scan reads roughly 25,000 times more data than the lookup, every single time.

Fanout also explains why indexes age so gracefully. Doubling the table does not add a level. Growing it by a factor of a few hundred adds one level, which costs each lookup exactly one extra page read. This is what logarithmic cost with a base of several hundred feels like in practice: effectively flat.

An index does not make the database faster. It gives the database permission to skip almost everything, and the planner only accepts the offer when your query's shape keeps the promise the index made.

Before and after, in the planner's own words

Here is the 10-million-row orders table, a lookup by reference code, and no index. EXPLAIN ANALYZE reports the damage:

Seq Scan on orders  (cost=0.00..225000.00 rows=1 width=96)
  Filter: (reference = 'KB-2049-1177')
  Rows Removed by Filter: 9999999
Planning Time: 0.108 ms
Execution Time: 912.402 ms

"Rows Removed by Filter: 9999999" is the entire story in one line: the database inspected ten million rows and discarded all but one. Add the index:

CREATE INDEX ix_orders_reference ON orders (reference);

Index Scan using ix_orders_reference on orders
  (cost=0.43..8.45 rows=1 width=96)
  Index Cond: (reference = 'KB-2049-1177')
Planning Time: 0.126 ms
Execution Time: 0.061 ms

From 912 ms to a fraction of a millisecond, without touching the query. The numbers here are rounded for readability, but the shape is exactly what you will see on your own tables: the scan's cost tracks the page count, and the index scan's cost tracks the tree's depth. If you work in EF Core and want the same skill applied to LINQ-generated SQL, reading query plans walks through it from that side.

When the planner ignores your index

Creating an index is a suggestion, not an instruction. The planner estimates the cost of using it against the cost of a plain scan and picks whichever it believes is cheaper. Three situations account for most "why is it not using my index" tickets.

The composite index is missing its leading column. A multi-column index is sorted by its first column, then by the second within equal values of the first. That ordering is only navigable if the query pins the first column down.

CREATE INDEX ix_orders_customer_created
    ON orders (customer_id, created_at);

-- can descend the tree: the leading column is pinned
WHERE customer_id = 42 AND created_at >= '2026-01-01'
WHERE customer_id = 42

-- cannot: created_at alone says nothing about where to start
WHERE created_at >= '2026-01-01'

A function wrapped the column. The index stores email, not lower(email). Wrap the column in any expression and the sorted order no longer applies to your predicate, so the tree cannot be descended. Either index the expression itself or normalize the data on write:

-- the plain index on (email) cannot serve this predicate
SELECT * FROM users WHERE lower(email) = '[email protected]';

-- an expression index can
CREATE INDEX ix_users_email_lower ON users (lower(email));

The predicate is not selective enough. An index on a status column with three distinct values does little for WHERE status = 'shipped' when a third of the table matches. Fetching millions of rows through an index means millions of scattered page reads, and one sequential pass over the table is genuinely cheaper. The planner refusing your index here is not a bug. It is arithmetic.

Covering indexes: never visiting the table at all

A normal index scan alternates between two structures: find the key in the index, then hop to the table page for the rest of the row. If the query only needs columns the index already contains, that hop is wasted motion. Postgres calls skipping it an index-only scan, and you can invite one deliberately by packing the extra columns into the index's leaf pages:

CREATE INDEX ix_orders_customer_total
    ON orders (customer_id) INCLUDE (total);

-- served entirely from index pages
SELECT total FROM orders WHERE customer_id = 42;

One caveat keeps this honest: Postgres still has to confirm each row is visible to your transaction, and for recently modified pages that means visiting the table anyway. Index-only scans shine on read-mostly data and fade on hot, churning tables.

Sorted leaf pages buy you one more thing for free: ranges and ordering. An ORDER BY created_at DESC LIMIT 20 can walk a few leaf pages instead of sorting the world, which is exactly the machinery that makes keyset pagination fast where OFFSET falls over.

The bill arrives at write time

Indexes are not free reading aids. Each one is a copy of part of your table that must be updated synchronously, inside the same transaction as the write. Every INSERT adds an entry to every index on the table. An UPDATE that touches an indexed column becomes a delete plus an insert inside that index, occasionally splitting a page and cascading upward. Five indexes turn one logical row write into maintenance on six structures, all of it logged for durability.

The practical rule: index the queries you actually run, and audit the collection occasionally. Postgres tracks usage in pg_stat_user_indexes, and an index with zero scans since the last deploy is pure write tax. The PostgreSQL manual's chapter on indexes is the primary source worth reading end to end when you want the full picture.

Reading plans until you can guess them

Everything above is knowable in an afternoon. The durable version of it, the reflex that guesses the plan before running EXPLAIN, only comes from watching plans respond to your own queries, repeatedly, with the row counts visible.

Katabench's database track runs that loop on every submission. Your code executes against a real PostgreSQL instance, and the grader reads the actual query plan, not just your rows. A query that gets the right answer by scanning the whole table fails the budget, with the plan on screen showing you why, right next to output that looks perfectly correct. Watch "correct but scanning everything" turn into "correct in a handful of pages" often enough and the leading-column rule stops being trivia. It becomes the thing your hands already know.