Insert into a Non-full Page - Indexes as Search Structures

Insertion into a page with room keeps keys ordered without splitting.

highlighted = computed this step

Insert into room

Insertion first finds the target page. If that page has room, the key is inserted in sorted position and no page split is needed. Note: filling a page is not the same as splitting it.

\text{non full insert}

Before insert

Before the insert, the recomputed height is 1 and the key count is 2. Note: the page has room.

h=1,\quad k=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.

After insert

After the insert, the recomputed height is still 1 and the page count is still 1. Note: the page is full now, but proactive splitting waits until a later descent through it.

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.

Summary

A non-full insert preserves order without changing height. Note: a page models a node; real B-trees tune fanout to disk; no I/O or perf claims.

\text{ordered insert}