B+Tree Indexes

Concept. A B+Tree index stores keys in sorted order in a balanced tree. It supports both point lookups and range scans (WHERE rating BETWEEN 4.0 AND 5.0) by scanning leaf pages in key order.

Intuition. Think of a dictionary: half a million words, but you never scan them all. You can jump to the right letter, the guide words at the top of each page narrow you to the right page. A B+Tree gives a database table that functionality. So when you query "find Songs between 'Lava' and 'Love'" it walks down the tree to ``Lava,'' then reads leaf pages in order until it passes ''Love.'' One descent, then a scan, not a tree walk per row.

Prerequisites. Index Fundamentals introduces (key, page#) pairs and pointers.

What a B+Tree Stores

A B+Tree indexes a table's data pages. Three layers of index nodes (root, internal, leaf) route a lookup down to the right page, and the leaves are linked left-to-right so a range scan can stream across them without going back to the root.

In this example, each song has a permanent catalog number (catalog_no), separate from its Spotify ID. (Imagine an industry-supplied number when a new song comes out.)

B+Tree on Songs.catalog_no. Five green data pages on the left hold rows. The tree on the right has a green root, three green internal nodes, and six green leaves. The purple trace shows the lookup path for key 12890: root → middle internal → leaf 11234-13788 → Page 3, where row 12: As It Was (12890) lives.

Figure 1. Data pages on disk store the Songs rows. The B+Tree on disk stores a root and internal nodes that route lookups to sorted leaves. Leaves store (key, data-page pointer) pairs and link left-to-right. For catalog_no = 12890 ("As It Was"), the root selects 5000..14999, the internal node selects 11234..13788, the leaf resolves 12890 → Page 3, and Page 3 contains the row. With no pages cached, the lookup reads three index pages and one data page: four IOs.

Walking a Range Query

The B+Tree finds the starting leaf, then streams across leaves until it passes the end key. The trace below walks 12000 ≤ catalog_no ≤ 14000.

Walking the range 12000 to 14000. The root chooses the middle subtree, the middle internal node chooses leaf 3, the query reads leaves 3 and 4 in order, then stops at 14001 in leaf 4. Data pages 3 and 4 are fetched. Total 6 IOs versus 160,000 for a full scan.

Figure 2. For 12000 ≤ catalog_no ≤ 14000, matching rows occupy data pages 3 and 4. The descent runs root → middle internal → Leaf 3, then follows leaf links. Leaf 3 yields 12890 and 13456. Leaf 4 yields 13789 and 13980. The next key in Leaf 4 is 14001, which exceeds 14000, so the scan stops without reading another leaf. The query reads 4 index pages and 2 data pages, 6 IOs total, versus roughly 160,000 for a full scan, about 27,000× fewer IOs.

The result is mostly sequential IO once the descent reaches the starting leaf, which makes range scans cheap on a B+Tree.

B+Trees: Few Reads, More Work on Writes

Fanout is the number of children per internal page. Higher fanout means fewer levels.

$$ f \approx \frac{\text{page size}}{\text{key size} + \text{pointer size}}, \qquad h \approx \left\lceil \log_f N \right\rceil $$

N = number of indexable keys; h = approximate number of index levels.

For 1 trillion keys and 8-byte pointers, ignoring headers and unused space:

Page size	Key size	Approx. fanout	Index levels
64 KB	8 B	4,096	4
64 KB	1 KB	63	7
64 MB	8 B	4.2 million	2
64 MB	1 KB	65,027	3

Reads: High fanout keeps the tree shallow. Point queries follow one path; range queries continue through sorted leaves.
Writes: Inserts update pages. Full pages split, and splits can propagate upward. Maintaining balance adds work under heavy writes.

The height estimate assumes similar internal-node and leaf capacities and full pages; occupancy and page overhead affect the actual height.

Notes: Index levels are not the full lookup cost: fetching a data page adds IO, while cached index pages avoid disk reads. In practice, the root will be cached because all lookups start from that. We will not cover the balancing algorithms in cs145. They work similar to how splits work with Btree balancing algorithms (in RAM), except a bit trickier because we need to manage our I/Os carefully.

What B+Trees Handle Well, and What They Don't

Handles well

WHERE user_id = 42
WHERE rating BETWEEN 4.0 AND 5.0
WHERE name LIKE 'Ali%'
ORDER BY created_at

Equality, ranges, prefix matching, and sorted scans. Anything that benefits from keys being in order.

Doesn't help

WHERE LOWER(name) = 'alice'
WHERE name LIKE '%son'
WHERE age != 30

Functions on the indexed column (the index is on name, not LOWER(name)), suffix matches, and non-equality !=. The tree can't narrow the search space, so it falls back to a scan.