Part 3 of 8 · 3 min read
How a B-tree finds a key
Pages that point to pages, the branching factor and how few steps are needed.
Think of a dictionary with thumb tabs. The tabs split the book into sections. Inside a section, the top of each page shows a range of words. The reader flips from tab to page to line in three steps, however big the dictionary.
A B-tree is built like this. The book describes it: one page is the root. It holds several keys and references to child pages, and each child covers a continuous range of keys. The keys between the references mark the borders of the ranges. A lookup starts at the root and follows the reference for the range that contains the key, down through the levels until it reaches a leaf page, which holds the individual keys and either the values or references to them.
B-tree
A B-tree is a tree of fixed-size pages that keeps keys sorted. Each page holds many keys and references to child pages. All leaf pages lie at the same depth.
Example: looking for key 251, the root says "keys 200 to 300 are under the third child". That page says "250 to 260 are under its fifth child". That leaf holds the key.
Branching factor
The branching factor is the number of child references in one page of a B-tree.
Example: a page that points to 500 children has a branching factor of 500.
In practice the branching factor is several hundred, the book says. This makes the tree very shallow.
A worked example. Pages are 4 KB, and the branching factor is 500. Here a level means a level of index pages, and the last step is the page that holds the data.
- Level 1 (the root): 1 page, with 500 references.
- Level 2: 500 pages, with 500 × 500 = 250,000 references.
- Level 3: 250,000 pages, with 250,000 × 500 = 125,000,000 references.
- Level 4: 125,000,000 pages, with 125,000,000 × 500 = 62,500,000,000 references to data pages.
- Capacity of four levels: 62,500,000,000 pages × 4,096 bytes ≈ 256 TB, the figure given in the book.
So a lookup in a database of 256 terabytes needs four index pages and then the data page. In real databases the root and the next level are kept in memory, so a lookup often costs one or two disk reads.
For 10 million rows with about 100 rows to a data page, the tree needs 100,000 data pages. Two levels of index pages reach 250,000 data pages, which is enough. So a lookup reads 2 index pages and 1 data page, 3 page reads.
Range queries are cheap, too. The keys are sorted, so a query for keys 100 to 200 finds the first key and then reads along the leaves. Many implementations add pointers from each leaf to its neighbours, as the book says, so a scan moves sideways without going back up.
Because the tree always stays balanced, a B-tree with n keys has depth proportional to the logarithm of n. Doubling the data adds almost nothing to the depth.
| Data | Data pages (100 rows each) | Index levels needed (branching 500) |
|---|---|---|
| 100,000 rows | 1,000 | 2 |
| 10 million rows | 100,000 | 2 |
| 1 billion rows | 10,000,000 | 3 |
Check yourself:
- With a branching factor of 100, how many data pages can three levels of index pages reach?
- Why does doubling the data barely change the cost of a lookup?