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
Present key
The present search visits 3 pages and uses 3 comparisons. Note: the highlighted pages show the recomputed path.
pages=3,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.
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
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.
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.