B-tree Insertion
Insert keys while preserving sorted order, balanced height, and controlled node splitting.
B-tree insertion becomes difficult when learners first encounter overflow, median promotion, and split propagation. The goal of this page is to make those structural changes clear, step by step, before students think about implementation details.
The key teaching flow is: insert in order → detect overflow → split the node → promote the median → continue upward if needed.
Quick Facts
Keys inside each node remain sorted from left to right.
When a node receives too many keys, it must split.
The middle key moves upward so order is preserved across the tree.
Insertion preserves balanced height, even when splits propagate upward.
Key Idea
B-tree insertion is not just “put the key somewhere.” It is a structural process that must preserve both sorted order and balance.
The most important mental model is: insert locally, but reason globally. A small change in one node can cause structural changes higher in the tree.
Visualization
This visualization shows the full insertion story: ordered insertion inside a node, overflow becoming visible, the median key moving upward, and the way splits can continue toward the root.
Watch actively: pause before a split, predict which key will be promoted, and decide whether the structural change will stop or continue upward.
How It Works
Follow the search path until the correct leaf or target node is reached.
Place the new key into the node while keeping the keys ordered.
If the node now holds too many keys, a split is required.
Promote the median key upward and redistribute the remaining keys into two nodes.
Why Overflow Matters
Overflow is the signal that the node can no longer store another key without restructuring.
The median is promoted because it preserves correct ordering between the two resulting nodes.
A split starts locally, but the promoted key may force changes in the parent as well.
If promotion reaches a full root, the tree gains a new level while staying balanced.
The Structural Pattern
Every split follows the same reusable logic:
Detect overflow
Highlight the median
Promote the median upward
Redistribute remaining keys
Reconnect children if needed
Check the parent for overflowSeeing this as a repeated pattern makes B-tree insertion much easier to understand than memorizing isolated cases.
Why It Matters
B-tree insertion teaches how local ordering rules can preserve large-scale structural balance.
Balanced growth helps B-trees keep search, insertion, and update operations efficient.
B-trees are widely used in indexing systems, making insertion logic practically important.
When learners understand overflow and promotion, they can predict tree changes instead of guessing.
Pseudocode
A common high-level version of B-tree insertion looks like this:
B-TREE-INSERT(T, k):
r = T.root
if r is full:
create new root s
make old root a child of s
SPLIT-CHILD(s, 0)
INSERT-NONFULL(s, k)
else:
INSERT-NONFULL(r, k)
INSERT-NONFULL(x, k):
if x is a leaf:
insert k into x in sorted order
else:
choose the correct child of x
if that child is full:
SPLIT-CHILD(x, child_index)
decide again which child should receive k
INSERT-NONFULL(correct_child, k)The important idea is that insertion tries to move downward into a node that can still accept a key, and splitting happens before the structure becomes invalid.
Common Confusions
No. The median is promoted because it preserves the correct partition between left and right keys.
Insertion adds a key. Splitting is the structural repair that happens only after overflow.
Not always. Promotion can cause the parent to overflow, which may trigger another split.
Root overflow does not break the tree. It creates a new root and increases the height by one.
Outcome
After this lesson, learners should be able to insert a key into a B-tree in sorted order, recognize overflow, explain why the median is promoted, and describe how split propagation preserves balance.