How a Database Index Finds a Row: the B-Tree, Step by Step

With no index, read everything

PostgreSQL stores a table in pages, fixed blocks of 8 KB. Our million rows fill 9,336 of them, in the order they arrived.

We left out the primary key on purpose, because a primary key builds an index for you. So nothing records where id 742001 lives, and nothing stops two rows from sharing it. The only way to answer is to check every row on every page.

The phone book trick

Now think of a paper phone book. You never read it from page one. The names are sorted, so you open it near the middle. Too far? Jump back. Every glance throws away a big part of the book. An index gives the database the same trick: a separate, sorted copy of one column, where each entry also holds the address of its full row in the table.

Sorted is not enough on its own

A single sorted list of a million ids would already help. Look at the middle, throw away the wrong half, repeat. A million halved 20 times comes down to one, so any id takes about 20 steps.

But each step can land on a different page, and reading a page from disk is slow. The fix is to let each step choose between hundreds of options instead of two.

A tree of pages

A B-tree does exactly that, and it is the index PostgreSQL builds unless you ask for another kind. It is a tree made of pages. The top page, the root, holds a few dividing values, called keys, that split all the ids into ranges.

Each key points down to a page that splits its range more finely. The bottom pages, the leaves, hold every id in order, each with its row's address.

Hundreds of keys per page

How many choices does one page give? We looked inside the index with pageinspect, a tool that ships with PostgreSQL. One leaf page held 367 ids and kept 808 bytes empty, because a new index fills its leaves only 90 percent, leaving room for later inserts.

So each level multiplies its reach by a few hundred, and the tree stays very short.

Following one key down

Now the lookup itself. PostgreSQL reads the root and compares 742001 with its keys to pick one page on the next level down. It reads that page and picks again. The third page is a leaf, where 742001 sits next to the address of its row: a page number in the table and a slot on that page. One more read fetches the row. Three pages of tree, one page of table.

4 pages instead of 9,336

We ran the query with the index on a freshly restarted server. The plan changed from Seq Scan to Index Scan. A second lookup in the same connection touched exactly 4 pages: root, middle, leaf and the table page.

The first lookup in a connection touched 7. The extra 3 went on PostgreSQL's own catalog, working out how to compare the number we typed with the bigint column. Typed as a bigint, even a first lookup touched 4. The full scan touched 9,336.

EXPLAIN (ANALYZE, BUFFERS, COSTS OFF)
SELECT * FROM users WHERE id = 742003;

-- Index Scan using users_id_idx on users (actual rows=1)
--   Index Cond: (id = 742003)
--   Buffers: shared hit=4

PostgreSQL 17.10, the second lookup in one connection. Timing columns removed.

Ten times the rows, same depth

What happens as the table grows? We built the same index on 100, 10,000, one million and ten million rows. The trees were 1, 2, 3 and 3 levels deep.

Three levels at a few hundred keys a page have room for tens of millions of ids, so ten million still fit. Only when that room runs out does the root split and the tree grow a level on top.

Ranges come almost free

The leaves are linked to their neighbours, left to right. For a range such as ids 500000 to 500099, PostgreSQL walks down once to the first id, then moves right along the leaves until it passes the last one. Those 100 rows cost 8 pages in our run. Greater than, less than, between and ORDER BY on the column all use the same sorted leaves.

When the index cannot help

An index stores each value exactly as written. Now ask for lower(email) = 'user742001@example.com', where lower() turns the email into small letters before comparing. The index holds the original emails, not lowercased ones, so it cannot help.

The planner, the part of PostgreSQL that decides how to run a query, went back to reading the whole table. On the plain email column, the index worked: 4 pages.

SELECT * FROM users
WHERE date(created_at) = '2025-06-01';

The bill arrives on every write

Indexes are not free. Every insert adds an entry to each index that covers the row, and an update usually does too, unless no indexed column changed and the new row fits on the same page. A full leaf page splits in two and adds a key to the page above.

In the lab behind our Database Indexing lesson, the same 200,000 inserts took 160 ms with no index and 751 ms with five.

When reading everything is right

An index wins when a query wants a small share of the rows. For a large share it loses: rows found through the tree can sit on many different pages, and reading every page once, in order, is cheaper.

In our indexing lab, on two million rows stored in random order, PostgreSQL used the index up to about 20 percent and read the whole table by 40 percent.

Pages, a short tree, and a bill

Rows live in 8 KB pages in whatever order they arrived. A B-tree index is a sorted copy of one column, kept as a short tree of pages with hundreds of keys on each leaf.

A lookup reads one page per level, then the row: 4 pages for one row out of a million. Wrap the column in a function and the tree is skipped, and writes pay to keep it current.