Searching — a cursor descends the tree — one page I/O per tree level

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
Try it
Predict
Capture

What to watch for

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

Highlighted lines are the ones running in the diagram right now.

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

Sources

Where this sits in Build a B-tree storage engine (SQLite-style)

Scene 04 of 11, in the Anatomy act — Pages, the tree of pages, and how a search descends.. 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.

Up next. Lookups are cheap: 3 page reads in a tree of millions. But every INSERT must also descend to its home leaf — and what happens when that leaf is FULL? The next scene splits a leaf for the first time.

All 11 scenes in Build a B-tree storage engine (SQLite-style) · Every curriculum

Built with Arqly

Every scene in Build a B-tree storage engine (SQLite-style) builds on the one before it.All 11 Build a B-tree storage engine (SQLite-style) scenes