B-tree Pages

Growing the Tree

A root split grows the B-tree upward.

highlighted = computed this step

The root can split

When the root is full and a new insert arrives, the tree grows upward. A new root is created and the old root is split below it. Note: this is the height-changing case.

root split\text{root split}

Before root split

Before the growing insert, recomputed height is 2 and page count is 5. Note: the root is full in the render, but height has not changed yet.

h=2,pages=5h=2,\quad \text{pages}=5

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 pages204060n010n130n250n37080n4

After root split

After the next insert, recomputed height is 3 and page count is 7. Note: the render shows the new top page.

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

A new top page appears

The old root had 3 keys, while the new root has 1 key. Note: those root key counts come from the compiled root nodes.

old root keys=3,new root keys=1\text{old root keys}=3,\quad \text{new root keys}=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.

B-tree pages204060n010n130n250n37080n4
B-tree pages40n020n110n230n360n450n5708090n6

Summary

Root split is how a B-tree increases height while keeping all leaves level. Note: a page models a node; real B-trees tune fanout to disk; no I/O or perf claims.

height grows\text{height grows}