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.

A leaf split can keep height

In the leaf-split contrast, recomputed height stays 2 while page count moves from 3 to 4. Note: the split adds a page without growing the root.

h=2,\quad \text{before pages}=3,\quad \text{after pages}=4

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}