B-tree Pages

Search is a Path

B-tree search follows one recomputed path of comparisons.

highlighted = computed this step

Search follows one path

A B-tree search does not scan every page. Each page comparison chooses one next page until the key is found or a leaf proves absence. Note: paths and comparison counts are recomputed by the engine.

root to leaf search\text{root to leaf search}

Present at the root

A root hit visits 1 page and uses 1 comparison. Note: success can stop before any leaf page.

pages=1,comparisons=1\text{pages}=1,\quad \text{comparisons}=1

a page models a node; real B-trees tune fanout to disk pages; tiny exact trees prove structure/search behavior only - no I/O or perf claims.

B-tree search 40: found; comparisons=1; path=n040n020n110n230n360n450n5708090n6

Present key

The present search visits 3 pages and uses 3 comparisons. Note: the highlighted pages show the recomputed path.

pages=3,comparisons=3\text{pages}=3,\quad \text{comparisons}=3

a page models a node; real B-trees tune fanout to disk pages; tiny exact trees prove structure/search behavior only - no I/O or perf claims.

B-tree search 70: found; comparisons=3; path=n0,n4,n640n020n110n230n360n450n5708090n6

Absent key

The absent search also visits 3 pages and uses 3 comparisons before stopping. Note: not found still has an exact path.

pages=3,comparisons=3\text{pages}=3,\quad \text{comparisons}=3

a page models a node; real B-trees tune fanout to disk pages; tiny exact trees prove structure/search behavior only - no I/O or perf claims.

B-tree search 55: not found; comparisons=3; path=n0,n4,n540n020n110n230n360n450n5708090n6

Summary

Search is a path plus a comparison count, whether it succeeds or fails. Note: a page models a node; real B-trees tune fanout to disk; no I/O or perf claims.

search path\text{search path}