B-Tree Insertion & Node Splitting

A new key always ends up in a leaf — B-trees never insert into internal nodes directly. The only complication is what to do when the target leaf (or a node on the path to it) is already full (has 2t − 1 keys). The answer is splitting.

Node split. A full node with 2t − 1 keys is divided into two nodes of t − 1 keys each, and its median key moves up into the parent as a separator. The parent gains one key and one child.

Because the median rises into the parent, splitting is the mechanism by which a B-tree grows upward. When the split reaches an already-full root, the root itself splits and a brand-new root is created — that is the only way a B-tree increases its height, which is why all leaves always stay at the same level.

Take a full node (t = 3, so 5 keys) [40, 50, 60, 70, 80] whose parent needs to gain a key here. The median is the middle key, at index t − 1 = 2, which is 60:

The left half keeps keys before the median, the right half keeps keys after it, and 60 is inserted into the parent between the two child pointers. Each half now has exactly t − 1 = 2 keys — the legal minimum — so both halves are valid B-tree nodes.

CLRS's trick — split on the way down. Rather than insert first and fix overflow afterward, the standard algorithm splits any full node the moment it is encountered while descending. This guarantees that when we finally reach the leaf, its parent is not full and can absorb a rising median — so a single downward pass suffices, with no need to walk back up.

Insert 10, 20, 5, 6, 12, 30, 7, 17, 3, 25, 40 into an empty B-tree of minimum degree t = 2 (so max 2t − 1 = 3 keys; a node is full at 3 keys). We split full nodes on the way down.

Splitting occurs at the insertions of 6, 17, 3, and 25. The splits at 6 and 25 are root splits — the only two operations that increased the tree's height. Here is the final tree:

Now insert 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150 into an empty B-tree of minimum degree t = 3 (max 5 keys; median is the 3rd key of a full node). We keep this tree for the deletion topic that follows.

Because the keys arrive in sorted order, every split happens on the right spine — but the tree still stays perfectly balanced:

Final tree after all 15 insertions (height 1 — just root + leaves):

Notice how a large minimum degree keeps the tree astonishingly flat: 15 keys fit in just two levels, and the root's 4 keys point to 5 leaves.

The insertion is a single top-down pass. B-TREE-SPLIT-CHILD divides a full child; B-TREE-INSERT-NONFULL places the key, splitting full children before descending so it is never blocked at a leaf.

Insertion touches the nodes on one root-to-leaf path and may split a node at each level, but every split is O(t) work. With height O(log_t n):

• Comparisons / CPU work: O(t · log_t n).
• Disk accesses: O(log_t n) reads down the path plus O(log_t n) writes for split nodes.

Crucially, most inserts cause no split at all — a split only happens when a node is full. This "rare, bounded restructuring" is exactly what makes the amortized cost so low, a theme we formalize later in this chapter.