Splitting a Full Page - Indexes as Search Structures

A full page splits when the next insert descends through it.

highlighted = computed this step

Split on the next descent

The engine uses proactive CLRS splitting. A full page can exist; it splits when the next insert has to descend through that full page. Note: the before and after trees show that timing.

\text{proactive split}

Full page before descent

Before the next insert, the recomputed height is 1 and the page count is 1. Note: the full page has not split yet.

h=1,\quad \text{pages}=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.

After the next insert

After the next insert descends through the full page, height becomes 2 and page count becomes 3. Note: the median is pushed up by the recomputed split.

h=2,\quad \text{pages}=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.

Summary

A split happens when insertion must pass through a full page, not one key early. Note: a page models a node; real B-trees tune fanout to disk; no I/O or perf claims.

\text{split timing}