Answers · Where the data lives

How does a B-tree find one row among millions in just a few reads?

In shortA B-tree finds a row by reading only a few pages: each page holds hundreds of pointers, so the tree stays three or four levels deep.

A B-tree finds one row by reading a handful of pages, not by scanning rows. Each page holds hundreds of sorted key-and-pointer pairs, so every page read divides the remaining candidates by that branching factor rather than by two.

b = \frac{p}{k+q} = \frac{8000}{8+8} = 500, \qquad b_{\text{practical}} \approx 300

The arithmetic of depth

Take a branching factor of 300. The bottom level holds the keys themselves, so one bottom page covers 300 keys. A page one level up points at 300 bottom pages, so it covers 300 × 300 = 90,000 keys. One level above that covers 300 × 90,000 = 27,000,000 keys. One more covers 300 × 27,000,000 = 8,100,000,000 keys. A table of millions therefore sits in three levels, and a table of billions sits in four. At each level the page you read chooses one child out of up to 300, so that one page read removes all the keys under the other 299 children.

FIG 1

levels	bottom pages	keys covered	real table needs this many
1	1	300	0
2	300	90,000	0
3	90,000	27,000,000	1
4	27,000,000	8,100,000,000	1

That is the whole reason the read count stays small. The tree does not store the row in every node. The bottom level holds every key exactly once, paired with the location of its row, and the upper levels hold copies of some keys as signposts. A lookup chooses one child at each signpost level and reaches a bottom page containing the key. Within that page it scans at most a few hundred entries, which is one page read, not millions of row reads. The row itself is not inside the signpost pages; only its address is, which is why the index can be much smaller than the table and still find any row.

The natural guess is that a tree with millions of rows must have millions of nodes to inspect, or that the depth must be enormous. Neither follows. Depth counts levels, not rows. If a page held only two children, a million keys would need about 20 levels, because 2^10 = 1024 and 2^20 = 1,048,576. With 300 children a page, three levels cover 27,000,000 keys. The same million keys need three index pages, not a million. The extra factor is the branching factor: each page is used to throw away 299 out of every 300 remaining possibilities.

What is actually read

The depth is not the same as the cost, because the top of the tree is tiny and hot. The root is one page and is read by every query that uses the index. The second level is 300 pages; at 8 kilobytes a page that is 300 × 8 = 2,400 kilobytes, or 2.4 megabytes. That fits in memory comfortably and stays there. The bottom level is 90,000 pages; at 8 kilobytes a page that is 90,000 × 8 = 720,000 kilobytes, or 720 megabytes. That is too large to keep wholly resident, so it is the first level that usually costs a storage read.

FIG 2One lookup and where each read comes from

step	step	page visited	size of that level	where it came from	what happened
1	1	root	1 page	memory	Read by every query, so always resident.
2	2	second level	300 pages	memory	300 × 8 KB = 2.4 MB, small enough to stay resident.
3	3	bottom level	90,000 pages	storage	90,000 × 8 KB = 720 MB, so usually the first storage read.
4	4	the row	244,000 pages	storage	244,000 × 8 KB = 1,952,000 KB, about 1.95 GB of table. The row fetch is scattered and often the dominant cost.

4 steps

The first two levels are small enough to stay resident. The bottom page and the row are the two reads that touch storage.

So a point lookup visits the root in memory, the second level in memory, one bottom page from storage, and then the row from storage. Two real reads, not four. A range query pays that descent once and then follows the links between neighbouring bottom pages, reading only the pages that contain matches. That is why the same structure serves both a single-row lookup and an ordered range.

Where the arithmetic stops being comfortable

The branching factor is not fixed at 300. It is p divided by k + q, so wider keys lower it. An 8-byte key and an 8-byte pointer give 8000 ÷ 16 = 500; a 100-byte text key gives 8000 ÷ 108 = 74.07, about 70. At 70 children a page, three levels cover 70 × 70 × 70 = 343,000 keys, so a million rows need four levels, not three. Real trees also leave slack in pages for later insertions, so the practical branching factor is lower than the packed arithmetic suggests. And the second read, fetching the row, can dominate when rows are large or scattered. A covering index, or a table organised so that the row fetch hits a page already in memory, changes that last cost without changing the tree.

Worth keeping

One page can hold hundreds of key and pointer pairs, so each level of a B-tree reduces the search by hundreds rather than by two.
The top levels of an index are small enough to stay in memory, so a lookup usually costs one read for a bottom index page and one read for the row.
The depth grows by one only when the number of keys grows about three-hundredfold.

Where this goes next

This question is one step of How an Index Actually Works, a course that works through its subject from the beginning. The page that teaches this part of it is The Tree Everything Uses, and it reads the whole way through whether or not you have an account.

What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.

Read that page The whole course