Searching in a B-Tree

Why B-Trees, not binary search trees?

Every real database index — SQLite, PostgreSQL, MySQL's InnoDB — is backed by a B-tree (or the closely related B+tree), not a binary search tree. The reason is disk. A binary tree with a million keys has ~20 levels, and each level is a pointer chase that can cost a disk seek. A B-tree with a branching factor of, say, 100 needs only 3 levels to hold a million keys. Fewer levels means fewer page reads means a faster lookup. The core design idea of a B-tree is: make each node as wide as one disk page, and keep the tree shallow and perfectly balanced.

The shape of a B-tree node

A B-tree of order M (sometimes defined slightly differently across textbooks — here, order M means at most M-1 keys per node) has two kinds of nodes:

• Internal nodes hold k sorted keys and k+1 child pointers. Child i contains all keys strictly between key i-1 and key i.
• Leaf nodes hold sorted keys but no children.

For example, an internal node [10, 20] has three children: one for keys < 10, one for keys between 10 and 20, and one for keys > 20. Every leaf sits at the same depth — that's what "balanced" means for a B-tree; there's no rebalancing step needed for search itself, only for insert/delete (later lessons).

The search algorithm

Searching a B-tree is a straightforward recursive (or iterative) descent from the root:

function search(node, key):
    i = binary_search(node.keys, key)   // find insertion point
    if node.keys[i] == key:
        return FOUND
    if node.is_leaf:
        return NOT_FOUND
    return search(node.children[i], key)

At each node you do a binary search over its (sorted, in-memory) key array — this is cheap, it's an array scan/binary search, not a disk operation. The expensive part in a real system is fetching each node from disk, which is exactly why B-trees keep nodes wide: wide nodes mean few levels mean few page fetches.

Building SEARCH_PATH for debugging

Your exercise asks for two commands: BTREE SEARCH <key> (just the verdict) and BTREE SEARCH_PATH <key> (the verdict and the path taken). The path is invaluable for debugging tree structure — it's how you'll visually confirm your insert/split logic in the next lesson actually produced a correct tree.

Print each visited node's key array, in root-to-leaf order, joined by →, ending in FOUND or NOT_FOUND:

[10,20] → [1,5] → FOUND
[10,20] → [12,15] → NOT_FOUND

Notice the second example: the search descended into [12,15] (the middle child of [10,20], holding keys between 10 and 20) and didn't find the key there, and since [12,15] is a leaf, the search terminates as NOT_FOUND without visiting anything else.

Edge cases to get right

• Root is a leaf. A brand-new tree with only a few keys is a single leaf node — your traversal must handle "root has no children" as a base case, not just recurse blindly.
• Key equals a node's key exactly. Don't fall through to a child if the key matches one already stored in an internal node — internal-node keys are real, searchable data, not just separators.
• Off-by-one child selection. With keys [10, 20], key 15 must go to child index 1 (the middle child), 5 to child index 0, and 25 to child index 2. Get this index arithmetic wrong and searches silently return wrong answers for a subset of keys.
• Empty tree. Searching before any insert should report NOT_FOUND cleanly, not crash.

Get search rock-solid first — every later B-tree lesson (insert, delete, splitting, rebalancing) depends on correctly walking root-to-leaf, and you'll reuse this exact traversal logic to locate the node where an insert or delete needs to happen.