B-Tree Search: Descending One Page at a Time

After this lesson you can look a key up in a B-tree, print the exact path the lookup took, and list every key in a range in sorted order. The path is the cost: each node on it is a page a real database would have to read.

The descent

Searching starts at the root and makes one decision per node, using the binary search from lesson 8 on that node's sorted keys.

1. Find i, the first position whose key is not smaller than the target.
2. If position i exists and holds the target: found, stop. Internal keys are real data, not just signposts, so a hit in an internal node is a hit.
3. Otherwise, if the node is a leaf the key is not in the tree.
4. Otherwise the target belongs between key i-1 and key i, which is exactly where child i lives. Continue in that child.

For keys [10, 20] the target 5 goes to child 0, 15 to child 1 and 25 to child 2. Using the lower bound in step 1 gives these indexes for free: it returns the count of keys smaller than the target.

            [10,20]
           /   |   \
      [1,5]  [12,15]  [25,30]

SEARCH_PATH 13:  [10,20] -> [12,15] -> NOT_FOUND
   at [10,20]: first key >= 13 is 20 (position 1), not equal, go to child 1
   at [12,15]: first key >= 13 is 15 (position 1), not equal, a leaf: stop
SEARCH_PATH 20:  [10,20] -> FOUND

The path lists every node read, root first, ending in the verdict. A hit in the root is a path of length one. An empty tree has no nodes to read, so it prints just NOT_FOUND.

Why this is fast

Within a node the work is a binary search in memory, which is cheap. Between nodes it is a pointer chase, and on disk each one is a page read. With 100 children per node, a million keys need about 3 levels, so any key is at most 3 page reads away. This is the number the quiz below asks about.

Range queries

BTREE RANGE lo hi lists every key k with lo <= k <= hi, ascending, separated by spaces, or (none). Because keys live in internal nodes too, the answer is an in-order walk: for each node, visit child 0, then key 0, then child 1, then key 1, and so on. Skip what cannot matter:

• In each node, start at the first key that is >= lo (a binary search again); the children to its left hold only smaller keys.
• Visit child i, then look at key i: stop the node as soon as that key is greater than hi, or as soon as the keys run out.

That visits the nodes on the path to lo, the nodes holding the answer, and the path to hi, never the rest of the tree. Cost: O(log n + k) for k results.

Commands and errors

BTREE SEARCH <key> prints FOUND or NOT_FOUND. BTREE SEARCH_PATH <key> prints the path with -> between items. A wrong number of arguments is ERR usage: BTREE <op> <key> (or <low> <high> for RANGE), and a non-integer is ERR bad number: <text>. Trees for the tests are built with BTREE LOAD, from the previous lesson.

Common mistakes

• Searching only the leaves. In a B-tree a key can live in an internal node: SEARCH_PATH 20 above ends at the root.
• Off-by-one child choice. With keys [10, 20], key 15 goes to child 1, not 0 or 2.
• Forgetting the empty tree. The root is a leaf with no keys; do not read from it.
• Collecting a range by scanning everything. Prune with lo and stop at hi.

Your exercise

The starter loads, prints and checks trees, and parses the commands. You write search (returning the nodes it read) and range_walk. The mistake to avoid: descending into the wrong child when the target is larger than every key in the node.