All Leaves Equal Depth - Indexes as Search Structures

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.

\text{balanced leaves}

Balanced tree

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

h=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.

Leaf depth

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

\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.

A smaller tree has the same rule

The smaller compiled tree has height 2, leaf count 3, and leaf depth 1. Note: equal-depth leaves are checked before rendering here too.

h=2,\quad \text{leaves}=3,\quad d=1

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

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.

\text{balanced search}