A Page is Ordered Keys - Indexes as Search Structures

A B-tree page stores ordered keys and supports exact comparison search.

highlighted = computed this step

A page stores ordered keys

An index page is a small ordered array of keys. Search compares against those keys in order, then either stops or chooses a child page. Note: this tiny book uses recomputed B-tree pages, not a storage engine.

\text{ordered page}

One page

The compiled tree has height 1, node count 1, and key count 3. Note: the page fills, but no split happens just because it is full.

h=1,\quad n=1,\quad k=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.

Exact comparisons

Searching inside the page uses exactly 2 recomputed comparisons. Note: the highlighted render, not prose, is the source of the key path.

\text{comparisons}=2

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

A page models a node: keys are ordered and comparisons are exact. Note: a page models a node; real B-trees tune fanout to disk; no I/O or perf claims.

\text{page model}