B-tree Pages

Honest by Construction

The B-tree and search path are recomputed before rendering.

highlighted = computed this step

Honest by construction

The lesson author supplies inserts and optional expected checks. The engine recomputes the tree and recomputes any search path before rendering. Note: an expected value can only reject a mismatch; it cannot create the answer.

recompute boundary\text{recompute boundary}

Compiled tree

The recomputed tree has key count 6. Note: the structure in the diagram comes from inserts, not an authored tree.

k=6k=6

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 pages2040n010n130n25060n3

Compiled search

The recomputed search uses 3 comparisons. Note: a wrong authored path is rejected during the lesson self-test.

comparisons=3\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 50: found; comparisons=3; path=n0,n32040n010n130n25060n3

Compiled scan

The recomputed scan emits 6 keys. Note: a wrong authored scan is rejected during the lesson self-test.

scan keys=6\text{scan keys}=6

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.

Recomputed scan - in-order scan; keys=6102030405060

Tamper guards

The self-test also rejects a wrong authored tree, a wrong authored search path, a wrong authored scan, and a derived height sidecar. Note: expected values can guard the recompute boundary, but cannot become rendered facts.

guards reject authored answers\text{guards reject authored answers}

Summary

The trust boundary is recompute first, then render. Note: a page models a node; real B-trees tune fanout to disk; no I/O or perf claims.

honest render\text{honest render}