B-tree Pages

All Leaves Equal Depth

A B-tree keeps every leaf at the same depth.

highlighted = computed this step

Leaves stay level

A B-tree keeps all leaves at the same depth. That balance is what keeps every search bounded by the tree height. Note: the invariant is checked on the recomputed tree.

balanced leaves\text{balanced leaves}

Balanced tree

The recomputed height is 3 with 7 pages. Note: every leaf sits at the same rendered level.

h=3,pages=7h=3,\quad \text{pages}=7

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

Leaf depth

There are 4 leaves, and each leaf has recomputed depth 2. Note: equal leaf depth is structural, not a caption guess.

leaves=4,d=2\text{leaves}=4,\quad d=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.

B-tree pages40n020n110n230n360n450n5708090n6

Summary

Balance means every search reaches a leaf at the same depth. Note: a page models a node; real B-trees tune fanout to disk; no I/O or perf claims.

balanced search\text{balanced search}