B-tree Pages

Ordered Scan

An in-order walk reads keys in sorted order.

highlighted = computed this step

Ordered scan reads in order

Search follows one path, but an ordered scan walks the tree in key order. The scan result is recomputed from the compiled tree, then rendered as a sequence. Note: the sequence appears only in the diagram.

in order scan\text{in order scan}

Tree source

The source tree has recomputed height 2 and key count 9. Note: the same compiled tree feeds the scan.

h=2,k=9h=2,\quad k=9

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 pages205070n010n13040n260n38090n4

Rendered scan

The recomputed scan emits 9 keys. Note: the render shows the sorted sequence without prose hand-typing it.

scan keys=9\text{scan keys}=9

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.

Ordered scan - in-order scan; keys=9102030405060708090

Scan endpoints are recomputed

The scan starts at 10 and ends at 90. Note: these endpoints are read from the compiled scan result.

first=10,last=90\text{first}=10,\quad \text{last}=90

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.

Ordered scan - in-order scan; keys=9102030405060708090

Different inserts, ordered output

The ascending-insert tree has recomputed height 3 and its scan emits 9 keys. Note: scan order comes from the tree traversal, not from prose.

h=3,scan keys=9h=3,\quad \text{scan keys}=9

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 pages40n020n110n230n360n450n5708090n6
Ordered scan from ascending inserts - in-order scan; keys=9102030405060708090

Summary

An ordered scan is deterministic because it is an in-order walk of the recomputed tree. Note: a page models a node; real B-trees tune fanout to disk; no I/O or perf claims.

scan summary\text{scan summary}