How B+ Trees Accelerate Searches: Step-by-Step IO Walkthrough

The figure above shows a B+ tree, where each part has three main concepts: physical disk blocks, data items (shown in blue), and pointers (shown in red).

For example, disk block 1 contains data items 17 and 35 and pointers P1, P2, P3. P1 points to a block with keys less than 17, P2 points to the block with keys between 17 and 35, and P3 points to the block with keys greater than 35.

The actual data records are stored in the leaf nodes: 3, 5, 9, 10, 13, 15, 28, 29, 36, 60, 75, 79, 90, 99.

Non‑leaf nodes do not store real data items; they only keep guide keys that direct the search, such as 17 and 35, which do not appear in the table itself.

B+ Tree Search Process

To find the key 29, the following steps occur:

Disk block 1 is loaded from disk into memory, incurring one I/O.

In memory, a binary search determines that 29 lies between 17 and 35, so pointer P2 is followed; the block addressed by P2 (disk block 3) is loaded, causing a second I/O.

Within block 3, binary search shows 29 lies between 26 and 30; pointer P2 of block 3 is followed, loading disk block 8 into memory, a third I/O.

A final binary search in memory finds 29, completing the query.

In total, three I/O operations are needed to locate the target data item.

A three‑level B+ tree can represent millions of records, providing a huge performance boost for queries.