B-Tree Search — Root to Leaf Traversal

Searching a B-tree is the core operation that makes databases fast. It combines the tree traversal of binary trees with the binary search within each node.

The Search Algorithm

function btree_search(node, key):
    i = binary_search_position(node.keys, key)

    if i < len(node.keys) and node.keys[i] == key:
        return FOUND    # key exists in this node

    if node.is_leaf:
        return NOT_FOUND    # reached a leaf without finding it

    # Follow the child pointer at position i
    return btree_search(node.children[i], key)

Visualizing the Search Path

Search for 15 in this tree:

            [20]
           /    \
      [5,10]   [25,30]

Step 1: Root [20] → 15 < 20 → go left
Step 2: Node [5,10] → 15 > 10 → but this is a leaf → NOT FOUND

Search path: [20] → [5,10] → NOT_FOUND

Search for 25:

Step 1: Root [20] → 25 >= 20 → go right
Step 2: Node [25,30] → 25 found at index 0 → FOUND

Search path: [20] → [25,30] → FOUND

Time Complexity

The height of a B-tree with n keys and order M is:

h = O(log_M(n))

At each level, we do O(log M) work for binary search within the node. Total:

O(log_M(n) * log(M)) = O(log(n))

For a million keys with order 100, the tree is only about 3 levels deep. Three page reads to find any key among a million.

The Search Path

Tracking the search path is useful for debugging and for understanding query plans:

BTREE SEARCH_PATH 15
→ [20] → [5,10] → NOT_FOUND

This shows exactly which nodes were visited. In a real database, each node visit is a page read from disk — the most expensive operation.

Binary Search Within a Node

The key operation at each node is finding where a key fits among the sorted keys. This determines either:

• The key is found (exact match)
• Which child to descend into (the child between two keys)

Node keys: [10, 20, 30]
Search for 25:
  Binary search → 25 falls between 20 and 30
  → follow children[2] (the third child pointer)

How PostgreSQL Searches B-Trees

PostgreSQL's _bt_search() function descends from root to leaf. At each page, _bt_binsrch() performs binary search. The function returns an "item pointer" to the exact tuple location. PostgreSQL also uses fence keys (high keys) to verify it hasn't overshot during concurrent modifications.

Your Task

Implement BTREE SEARCH for existence checks and BTREE SEARCH_PATH to show the traversal path.