Course contents
On this page
Why not just keep every key in one sorted list?
Derive the need for a page-based search tree from scanning, binary search, and insertion.
Our scan function checks rows one at a time. If the requested key is absent, it checks every row. With eight keys that is manageable. With millions, we should ask whether each comparison can rule out more than one candidate.
Sorting provides that opportunity. Consider these eight product IDs:
10 12 18 20 27 33 40 46We want 27. Because the keys are sorted, comparing it with a middle key tells us which side can still contain it. This is binary search: repeatedly narrow the candidate interval using its midpoint.
Follow the comparisons
Use zero-based positions 0 through 7 and choose the lower midpoint whenever two middle positions are possible.
- Positions 0 through 7
Middle position 3 contains 20. Since 27 is larger, keep positions 4 through 7.
- Positions 4 through 7
Middle position 5 contains 33. Since 27 is smaller, keep position 4.
- Position 4
It contains 27. The search succeeds after three comparisons.
A scan of this list would compare five keys before reaching 27. Binary search used three. This example shows the mechanism; it is not a benchmark of two database engines.
Change the operation to insertion
Now insert 19. In a packed sorted array, 19 belongs between 18 and 20. To open that position, the suffix containing 20, 27, 33, 40, and 46 must move. Repeating such moves for a large changing collection can be costly.
The page lesson adds another concern. A file larger than memory is accessed in pieces. Few comparisons do not automatically mean few storage reads: the compared keys might occupy different pages. We need a structure that makes useful decisions with each page we load.
Keep small sorted groups and route between them
Instead of one packed array, imagine sorted leaf pages holding groups of entries. A routing page stores boundary keys and references to the leaf pages. Reading one routing page tells us which group could contain the key.
When a leaf fills up, we can split that group and adjust its routing information rather than shift the entire remaining collection. Splits can propagate upward, so this is not free. The benefit is that the structure manages changes through pages while preserving search order.
That is the problem a B+ tree addresses. The next lesson will show the actual routing rules. We have introduced it because of read and update costs, not because every lookup requires a tree. A small table can still be cheap to scan.
Predict a miss
Using the midpoint rule above, search the original list for 19. Which keys are compared?
Follow the remaining interval
Compare 20 at position 3, then 12 at position 1, then 18 at position 2. After 18, the remaining interval is empty, so report absence. The sorted order proves that 19 cannot be hiding elsewhere in the list.
Do not return the nearest key. A lookup for 19 must distinguish “not present” from “18 is close.”
Further reading
MIT 6.006 lecture notes develop search and data-structure costs. CMU’s index notes explain the page-oriented tree we will visit next.