Keep several separators in one node
A binary search tree stores one key per node. A B-tree stores several sorted keys in each node, with one child interval between successive keys and one at either end. A single node can therefore direct a search among many subtrees. This is useful when reading a whole block of keys is much cheaper than making many separate storage accesses.
High branching alone does not guarantee a short tree. B-trees also impose lower occupancy bounds and require every leaf to have the same depth. Insertion must preserve all these conditions while making room for a new key. We will use top-down insertion: split a full child before entering it, so the recursive call always starts with space available.
The abstract object here is a set of distinct keys with a total order.
contains(x) tests membership and insert(x) adds if absent. A
repeated insertion leaves both the set and, in our implementation, the
tree unchanged. Values associated with keys or repeated-key multisets
would need additional rules.
Equality and the comparisons used by LOWER_BOUND must agree with this
same total order. The CPU cost model below counts each key comparison
or key/pointer move as constant work.
State the minimum-degree convention
Definition 8.1.1
(B-tree of minimum degree t)
Fix an integer . Every completed tree obeys these invariants:
- A node with keys stores them in strictly increasing order. It has either no children, making it a leaf, or exactly children.
- Every nonroot node has between and keys. A nonempty root has between 1 and keys. The empty tree is one empty leaf root.
- All keys in a child subtree lie in the interval specified by the surrounding node keys. For keys , child 0 contains keys below ; child , for , contains keys strictly between and ; child contains keys above .
- Every leaf has the same depth, counting root-to-leaf edges.
A node with keys is full. A nonroot internal node has at least children and at most . For , nodes have one, two or three keys; this is often called a 2–3–4 tree.
Terminology such as “order” varies between descriptions of B-trees. We will use the explicit minimum degree throughout. A 2–3 tree permits only one or two keys per node and is not the same capacity convention as the B-tree here.
The separators themselves are stored set members, including keys inside internal nodes. They are not merely copies of keys that must also remain in leaves. B+ trees use different record-placement conventions; their leaf-copy rules should not be imported into this insertion algorithm.
Search one interval at each step
Let LOWER_BOUND(keys,x) return the first index whose key is at least
x, or the length of the array if every key is smaller. Use zero-based
indices for both keys and children.
CONTAINS(node, x):
i = LOWER_BOUND(node.keys, x)
if i < number of node.keys and node.keys[i] == x:
return true
if node is a leaf:
return false
return CONTAINS(node.children[i], x)
Proof X-ray
Why no other subtree needs to be searched
If a node key equals , the set member has been found even if the node is internal. Otherwise, lower bound identifies the unique interval in which could occur. Every other child subtree contains only keys strictly outside that interval, by the range invariant.
Descending into that one child therefore preserves the statement “if is stored and not already found, it is in this subtree”. Reaching a leaf without equality proves absence. Each recursive step moves down one level in a finite tree, so the search terminates.
Split a full child while its parent has room
Suppose parent has fewer than keys, and its child at index is a full node with keys . Promote the median into parent slot . Leave in , and put into a new right sibling . Both children now have keys.
If was internal, its old children must also be divided: keeps child indices , and receives indices . Move whole subtrees, retaining their internal structure. If was a leaf, both resulting nodes remain leaves.
SPLIT_CHILD(P, i): // P has room; child i is full
Y = P.children[i]
median = Y.keys[t-1]
Z = a new node with the same leaf status as Y
Z.keys = a copy of Y.keys[t .. 2t-2]
if Y is not a leaf:
Z.children = Y.children[t .. 2t-1]
Y.children = Y.children[0 .. t-1]
Y.keys = Y.keys[0 .. t-2]
insert median into P.keys at index i
insert Z into P.children at index i+1
Array slices here construct the indicated new arrays; changing the left
node must not accidentally erase data still needed by the right node.
P.children[i] remains the left node . The median is removed from
the split node and stored once in ; neither resulting child keeps it.
Lemma 8.1.2
(Splitting a full child)
Let be a node with at most keys in a B-tree of minimum degree , and let its child be full. After SPLIT_CHILD(P, i) the same set of keys is stored; and the new sibling each have keys; has one more key and one more child; the order and interval conditions hold throughout; and every leaf below keeps its depth.
Proof
(Splitting preserves the set, intervals and balanced depth)
The keys of are partitioned into left keys, the median and right keys, so every old key remains exactly once. Both children have keys, within the legal range. The parent's key count increases by one but remains at most because it had room. Its child count also increases by one, preserving “children = keys + 1”.
Every left key is below the median and every right key is above it. For internal nodes, the first old child intervals belong on the left and the last on the right. The whole old subtree already lay between the appropriate neighboring keys in , so inserting its median keeps the parent's other intervals valid as well.
The two replacement nodes occupy the old child's level. Their descendant subtrees are moved without changing their heights. Thus every leaf retains its old depth. The split changes branching and key placement, while preserving the represented set and balanced leaf level.
Concept lensStructural
A split regroups keys but keeps their order
List a subtree as child , key , child , key , and so on, expanding each child in the same way. By the interval invariant, this reads the stored keys in increasing order. A split does not change that sequence: the median, which lay between the two halves of , now stands between and in the parent. Only the grouping of the sequence into nodes changes.
Common mistake
(Leaving the median in the split node)
Writing the median into the parent but not removing it from stores that key twice. For and , keeping in gives left node , right node and parent key . Child 0 must contain only keys strictly below its separator, yet it contains ; and now has keys instead of . The median moves up: it leaves and is stored once in . Copying a separator into a leaf is a B+ tree convention that does not apply here.
Split before descending, including at the root
We first search for the new key; that membership search changes no tree node. This makes a duplicate insertion leave the tree unchanged before any structural modification. The helper below therefore has two preconditions: the key is absent from the whole tree, and the node receiving the call is nonfull.
INSERT(x):
if CONTAINS(root, x):
return false
if root is full:
oldRoot = root
root = a new internal node with no keys and child [oldRoot]
SPLIT_CHILD(root, 0)
INSERT_NONFULL(root, x)
return true
INSERT_NONFULL(node, x):
i = LOWER_BOUND(node.keys, x)
if node is a leaf:
insert x into node.keys at index i
return
if node.children[i] is full:
SPLIT_CHILD(node, i)
if x > node.keys[i]:
i = i + 1
INSERT_NONFULL(node.children[i], x)
After a split, compare with the newly promoted median to decide between the left and right child. Equality cannot occur because was absent before insertion and splitting introduces no new keys.
Common mistake
(Descending into the child chosen before the split)
Take , parent with full middle child , and insert . Before the split, LOWER_BOUND gives . The split promotes , so the parent becomes with children , in positions 1 and 2. If the code keeps , it inserts into , producing below the separator . A later search for compares with , goes to child 2, the node , and wrongly reports absence. After a split, compare with the promoted median and increase when is larger.
The temporary new root with no keys is a work record immediately before its split. After the split it has one key and two children, satisfying the completed-tree invariant. Only a root split increases the height: all former leaves become one level deeper together.
Counterexample mode
Splitting a child of a full parent
A tempting claim is that a full child can be split whatever its parent looks like. Take , the full parent and its full child . Splitting promotes , and the parent would become , with four keys although . The lemma needs room in the parent. The descent supplies it by splitting each full child before entering it, so every node entered is nonfull; the root, which has no parent, is split below a new root.
Theorem 8.1.3
(Top-down insertion is correct)
Let a B-tree of minimum degree represent a finite set , and let be a key. If , INSERT(x) returns false and changes nothing. Otherwise it returns true, and the resulting tree is a B-tree of minimum degree that represents .
Proof
(Induction along the descent)
If , the membership test returns before any node is modified. Otherwise, a root split is an instance of the splitting lemma for a parent with no keys, so afterwards the tree is again valid for and its root is nonfull. Every later split is also an instance of the lemma, so it preserves the set and all invariants, and the recursion always enters a nonfull node. After each split, is compared with the new separator, so the chosen child interval contains . The final leaf insertion places at its LOWER_BOUND position, which keeps the keys strictly increasing, in a leaf that now has at most keys. Hence the tree represents and obeys every invariant.
Proof X-ray
Why top-down insertion cannot overflow a node
The root is nonfull when the helper starts: either it was already so, or it has just been replaced by a one-key root. At each internal call, the chosen child is either already nonfull or is split before descent. The parent can accommodate that promotion because it was nonfull on entry. It may become full afterwards, but this insertion descends only once from that parent and needs no second promotion into it.
The recursive call again enters a nonfull node. Eventually a leaf with at most keys receives one new key, so its final count is at most . The range comparisons place that key in the correct interval; all splits preserve the old set and balanced depth. Thus the result represents exactly the old set together with and obeys all invariants. This is why no overflow needs to be propagated back up the recursion.
A complete degree-two insertion trace
Worked example 8.1.4
(Insert 1 through 10 with t = 2)
Start from the empty leaf root. Nodes can hold at most three keys.
| Key inserted | Root afterwards | Structural event before the leaf insertion |
|---|---|---|
| 1 | [1] | None |
| 2 | [1,2] | None |
| 3 | [1,2,3] | None |
| 4 | [2] | Split the full root; promote 2 |
| 5 | [2] | None |
| 6 | [2,4] | Split the right child; promote 4 |
| 7 | [2,4] | None |
| 8 | [2,4,6] | Split the rightmost child; promote 6 |
| 9 | [4] | Split the full root; promote 4; insert 9 into [7,8,9] |
| 10 | [4] | Split grandchild [7,8,9]; promote 8; insert 10 into [9,10] |
After inserting 4, the tree is
[2]
/ \
[1] [3,4]
After inserting 8, it is
[2,4,6]
/ | | \
[1] [3] [5] [7,8]
After inserting 10, it is
[4]
/ \
[2] [6,8]
/ \ / | \
[1] [3] [5] [7] [9,10]
For the ninth insertion, the old root was full even though the destination leaf still had room. The chosen algorithm splits that root first anyway. It preserves the B-tree invariants but does not promise the smallest possible height among all representations of the same set.
The explorer below replays this insertion history, and others, one atomic split at a time, and checks every displayed snapshot against the B-tree invariants.
Worked example 8.1.5
(A duplicate and a full root, for t = 2)
Let the root be the full leaf . Calling INSERT(2) first runs CONTAINS, which finds at index 1 and returns true. So INSERT returns false and leaves the full root unchanged, with no split at all.
Calling INSERT(4) finds absent. The root is full, so a new empty root with child is made and split: the median is promoted, leaving children and . In INSERT_NONFULL on root , LOWER_BOUND gives ; child is nonfull, so no further split occurs, and is inserted into that leaf. The result is root with leaves and , the same tree as in the trace above. The two calls differ only in the membership test: the structural change occurs only for an absent key.
Occupancy gives a logarithmic height bound
Theorem 8.1.6
(Height versus the number of keys)
Let a nonempty B-tree of minimum degree have height , counted in edges, and keys. Then
Proof
(Counting nodes level by level)
For , the root has at least one key and two children. Each nonroot internal node has at least children. Therefore level contains at least nodes, each with at least keys. Summing levels gives
For , the same lower bound says . Taking logarithms in gives .
At the other extreme, level has at most nodes, each with at most keys, so . These bounds use key counts, not just the number of nodes. The empty leaf root is handled separately.
Counterexample mode
Equal leaf depth cannot be dropped
Suppose someone claims that the occupancy bounds alone, between and keys in each nonroot node, already give , even if leaves lie at different depths. For , take root with children and , and give the children and . Every node has one key, every internal node has one more child than keys, and the interval conditions hold. But the longest path has edges while , and the bound would need . Continuing the pattern to the right gives keys at height , which is linear in . Invariant 4 is what forces every root-to-leaf path to have the full number of levels.
Worked example 8.1.7
(Which heights are possible for 40 keys when t = 3?)
The theorem requires . For the lower bound is , so height 3 or more is impossible. For the upper bound is , so height at most 1 is impossible. For the bounds are . Hence every B-tree of minimum degree 3 with 40 keys has height exactly 2.
The edge case is : with the upper bound is attained only by a root with five keys and six full leaves of five keys each. One more key, , already forces .
With a linear scan inside each node, search uses comparisons. Binary search reduces that to comparisons, but inserting into node arrays and splitting can still move keys or pointers. The straightforward insertion algorithm, including the membership precheck, takes CPU work in the worst case, hence . For fixed , this is . The membership precheck and the insertion are two descents; the constant factor does not change these bounds.
Choose so a full node's keys and child references fit in one storage block. Under that model, a root-to-leaf descent reads blocks. A split touches only a constant number of node blocks at that level, so insertion also has block accesses under this model, or , including writes and the preliminary search. A split may write its parent and two resulting children, a constant number of blocks. Even without reusing the preliminary search's blocks, the two descents retain the same asymptotic bound. This block count does not say that searching or rearranging all keys inside a block is constant CPU work. The representation and cost model must be stated together.
Deletion needs additional borrowing, merging and possible root contraction to restore lower occupancy. It is not implemented by reversing the leaf insertion above. Our proofs and trace cover search and insertion only.
Solved exercises
Quick check
(1. Split an internal node, including its children)
Let . A parent has keys [5,60]; its middle child at index 1 is full, with
keys [10,20,30,40,50] and children in order.
After splitting that child, give the parent keys, both resulting key
arrays and the child lists assigned to them.
Solution · Solution 1
Promote the median 30, giving parent keys [5,30,60]. The left node
has [10,20] with children ; the new right node has
[40,50] with children . Each has keys and
children. The parent's other outer children remain unchanged.
The key 30 is stored once in the parent, not copied into either child.
Quick check
(2. Search for an internal key, a leaf key and an absent key)
Use the final ten-key tree. Trace membership queries for 2, 7 and 11, giving the node arrays examined and the reason each search terminates.
Solution · Solution 2
For 2, visit [4] then [2], where equality proves membership without
descending further. For 7, visit [4], [6,8], then [7], where it
is found. For 11, visit [4], [6,8], then [9,10]; all leaf keys
are smaller, and there is no child to search, so the answer is false.
Quick check
(3. A height bound is not a minimum-height guarantee)
For , can a height-two tree contain only six keys? Could the set also have a valid height-one representation despite the trace ending at height two?
Solution · Solution 3
Height two needs at least keys, so six is impossible.
The ten-key set can have root [3,6,9] with leaf children [1,2],
[4,5], [7,8] and [10]. It satisfies every occupancy and range
condition at height one. Top-down splitting gives a correct balanced
tree, not necessarily a minimum-height layout for the given key set.
Quick check
(4. The parent can become full before descent)
Let and parent keys be [10,30], with full middle leaf
[12,18,25]. The parent is nonfull, and the rest of the tree is valid. Insert the absent
key 20 by the helper. Give the new parent and middle-region leaves.
Then explain what a repeated public insert(20) does.
Solution · Solution 4
Split before descent: promote 18, so the parent becomes [10,18,30],
and the split leaves are [12] and [25]. Since , descend into
the right one and insert to obtain [20,25]. The now-full parent is
legal and needs no further promotion during this operation. A repeated
public insertion first finds 20 and returns false before any split,
leaving even a full root unchanged.