Searching — a cursor descends the tree — Build a B-tree storage engine (SQLite-style)

Build a B-tree storage engine (SQLite-style) (11 scenes)

Scene 04 · Searching — a cursor descends the tree

A point query reads exactly ONE page per tree level — three I/Os to find one row in a tree of millions, even on a miss.

Previously

Scene 3 left you with a static tree — labeled, sized, but never used. Now we run our first SELECT through it and count pages read.

Scene 04

Searching — a cursor descends the tree

Watch

Diagram

The same 3-level tree from scene 3, now with a **cursor** marker descending from root → interior → leaf. At each visited page the cursor highlights the **separator keys** it binary-searches, then drops into the chosen child. An **I/O counter** in the corner increments per page read; the side panel logs each step in plain English. Unvisited pages stay dim so the 3-page cost is visible.

Sources

SELECT WHERE id=42. The cursor lands on the root, binary-searches its separator keys, picks one child, and drops down. Each visited page is one disk I/O. Watch the counter.

Implementation

Btree.search(root_page, target)

one page read per tree level — depth = I/O count

1def search(root_page, target):
2    cursor = read_page(root_page)   # +1 I/O at root
3    io_count = 1
4    while cursor.is_interior:
5        child_idx = binary_search(cursor.keys, target)
6        cursor = read_page(cursor.children[child_idx])
7        io_count += 1                # +1 I/O per level
8    return scan_leaf(cursor, target) # local scan, no I/O

Page.binary_search(keys, target)

narrow [lo, hi) until lo names the chosen child slot

1def binary_search(keys, target):
2    lo, hi = 0, len(keys)
3    while lo < hi:
4        mid = (lo + hi) // 2
5        if target < keys[mid]:
6            hi = mid              # target lives in left half
7        else:
8            lo = mid + 1          # target lives in right half
9    # missing keys land past every separator → rightmost child
10    return lo                     # index of the chosen child

PreviousPages linked into a tree NextInsert and split — the tree grows