When a B-tree node overflows during insert, what happens, and how does the tree get taller?
answer
- think about where the extra room comes from
- one key does not stay in either half
- the parent gains something
- which node has no parent to promote into?
- growth happens at the top, never at one branch
basics
~20 sA full node splits in half at its median key: the two halves become sibling nodes and the median moves up into the parent as a separator. Splits cascade upward, and only a split of the root adds a level, so every leaf stays at the same depth.
solid answer
~40 sInsertion walks down to a leaf. If a node is full — with minimum degree `t` that means `2t-1` keys — it splits: the lower `t-1` keys stay, the upper `t-1` keys move into a new sibling, and the single median key is promoted into the parent as the separator between them. Promotion can overflow the parent, so splits cascade upward. If the cascade reaches a full root, a brand-new root is allocated holding one key and two children, and that is the **only** event that increases height. Because growth happens at the top rather than by lengthening one branch, all leaves remain at exactly the same depth without any rotation machinery. Together with the rule that every non-root node keeps at least `t-1` keys, this bounds height at O(log_t n).
code
pseudocode · 13 lines// c = x.child[i] is full: it holds exactly 2t-1 keys
split_child(x, i):
c = x.child[i]
z = new_node()
z.leaf = c.leaf
median = c.key[t-1] // the single key that moves up
move c.key[t .. 2t-2] into z.key[0 .. t-2] // upper t-1 keys
if not c.leaf:
move c.child[t .. 2t-1] into z.child[0 .. t-1]
shrink c to its lower t-1 keys (and t children)
insert median into x.key at position i
insert z into x.child at position i+1
// c and z now hold t-1 keys each; x gained one keygo deeper
Recall the one-sentence version: a full node splits in half and its middle key moves up to the parent. Know that leaves all sit at the same depth.
Be able to count keys through a split with minimum degree t — t-1 left, t-1 right, one promoted — and explain that only a root split adds a level, which is why no rotations are needed.
Show judgment about the two descent strategies and their write cost, and be able to describe the deletion mirror image (borrow from a sibling, otherwise merge) without being prompted.
Own the argument that the split rule turns a balance property into a structural guarantee, so no insertion order can degrade the tree, and be ready to weigh that predictability against structures that trade it for lower write amplification.
## The shape a B-tree maintains A B-tree is parameterised by a **minimum degree** `t` (at least 2). Every node other than the root holds between `t-1` and `2t-1` keys, and a node with `k` keys has exactly `k+1` children. Keys inside a node are sorted, and the child between two adjacent keys holds exactly the values that fall between them. Two structural invariants matter for this question: 1. **Occupancy floor.** Every non-root node holds at least `t-1` keys. This is what makes the fanout real rather than nominal — without it, a tree of 500-key-capacity nodes each holding one key would have the height of a binary tree. 2. **Uniform leaf depth.** Every leaf sits at exactly the same distance from the root. This is why worst-case and best-case lookups cost the same number of fetches. Splitting is the mechanism that preserves both while the tree grows. ## The split itself When a node holds its maximum `2t-1` keys and something must be inserted into it, the node is cut into three pieces: - the lower `t-1` keys (and their `t` children, if any) stay in the original node; - the upper `t-1` keys (and their `t` children) move into a freshly allocated sibling; - the one **median** key, the key at index `t-1`, does not stay in either half — it is **promoted** into the parent, inserted between the pointer to the original node and a new pointer to the sibling. Count it: `(t-1) + 1 + (t-1) = 2t-1`. No key is lost and none is duplicated. Both halves land at exactly the legal minimum, so the occupancy floor holds immediately after the split. The parent gains one key and one child pointer. Note that a split is a purely local operation: it touches the node, one new node, and the parent. It never rewrites a subtree and never moves a key more than one level. ## Cascading, and the one event that adds a level The parent may itself have been full. Then it splits by the same rule, promoting its own median one level further up. In the worst case, splits cascade all the way to the root. When the **root** is full, there is no parent to promote into, so a new root is allocated. It holds a single key — the promoted median — and two children: the two halves of the old root. Every existing leaf is now one level further from the root, but all of them moved together. This is the observation the question is really after: **a B-tree grows at the root, not at the leaves.** A binary search tree gets taller by extending one branch downward, which is why it needs rotations to stay balanced. A B-tree cannot extend one branch, because the only way to add a level is to raise the root, and raising the root deepens every path by exactly one. Uniform leaf depth is therefore a consequence of the growth rule, not something a separate rebalancing pass has to restore. There are no rotations in a B-tree. ## Two ways to run the descent There are two standard insertion strategies, and being able to name both reads as depth: - **Preemptive (single-pass) splitting.** On the way down, split *any* full node you pass through, whether or not the insert would have overflowed it. This guarantees the node you arrive at always has room for a promoted key, so the insert needs one downward pass and no parent pointers or recursion stack. The cost is splitting some nodes that did not strictly need it, which slightly lowers average occupancy. - **Split on the way back up.** Insert into the leaf, then split and propagate only if the leaf actually overflowed. This splits strictly less, but the algorithm needs a way back to the parent — a recursion stack or stored parent pointers. Both produce a valid B-tree; they differ in write amplification and in how much state the traversal carries. ## Why the height bound follows With the occupancy floor of `t-1` keys per non-root node, a tree of height `h` holds at least `2 * t^(h-1) - 1` keys. Inverting that gives `h <= log_t((n+1)/2) + 1`, so height is O(log_t n). Because `t` is chosen from the page size and lands in the hundreds, the base of that logarithm is large, and the height stays tiny even for enormous `n`. The split rule is exactly what makes this a guarantee rather than an average-case hope: no insertion sequence, however adversarial its ordering, can produce an unbalanced B-tree — unlike an unbalanced binary search tree, where sorted input degrades operations to O(n). ## The mirror case Deletion runs the same machinery in reverse. When a node drops below `t-1` keys it either **borrows** a key from an adjacent sibling (rotating a separator down from the parent and a key up from the sibling) or **merges** with a sibling, pulling the separator down and freeing a node. If the root ends up with no keys, its single remaining child becomes the new root, and the tree loses a level — again, only at the top.
- What is the minimum-occupancy rule, and why does the height bound depend on it?Every node except the root must hold at least `t-1` keys. Without that floor, nodes could sit almost empty and a tree with huge node capacity would still be deep, because height depends on the *actual* branching factor rather than the capacity. The floor guarantees a tree of height `h` holds at least about `2 * t^(h-1)` keys, which inverts to a height of O(log_t n).
- Does splitting eagerly on the way down differ from splitting on the way back up?Yes. Preemptive splitting splits every full node encountered during the descent, so insertion is a single downward pass needing no parent pointers or stack — at the price of splitting nodes that would not have overflowed. Splitting on the way back up performs strictly fewer splits and packs nodes more densely, but the algorithm must be able to return to each parent.
- Why does a B-tree need no rotations while balanced binary search trees do?A binary search tree gets taller by extending one path, so it needs rotations to move that path's excess height elsewhere. A B-tree can only get taller by allocating a new root, which deepens every path by one simultaneously. Uniform leaf depth is preserved by the growth rule itself, so there is nothing for a rotation to fix.
saying these in an interview costs you the question
- says the median key is copied into both halves
- thinks the tree grows downward by deepening one branch
- describes rotations, confusing B-trees with height-balanced binary trees
- claims every insert into a full node adds a level
- forgets that a split also moves child pointers, not just keys