Consider the B+ tree in the adjoining figure, where each node has at most two…
2007
Consider the B+ tree in the adjoining figure, where each node has at most two keys and three links.
Keys K15 and then K25 are inserted into this tree in that order. Exactly how many of the following nodes (disregarding the links) will be present in the tree after the two insertions?
Answer: A. 1 — A B+ tree in which every node holds at most two keys and three child pointers has order 3: whenever an insertion pushes a node's key count past two, that node…
- A.
1
- B.
2
- C.
3
- D.
4
Attempted by 103 students.
Show answer & explanation
Correct answer: A
A B+ tree in which every node holds at most two keys and three child pointers has order 3: whenever an insertion pushes a node's key count past two, that node splits. A LEAF split divides its keys between two new leaves and COPIES the first key of the right leaf upward into the parent as a separator (leaf keys are never removed on a leaf split, only duplicated up). An INTERNAL node split instead MOVES its middle key up into the parent, removing it from the split node; if that promotion itself overflows the parent, the split propagates further up, and a new root is created if the propagation reaches the top.
Insert K15: it belongs in the leaf {K10, K20}, giving {K10, K15, K20} — three keys, an overflow. The leaf splits into {K10} and {K15, K20}, and K15 (the first key of the right leaf) is copied up into the parent, which held only K30 and now holds {K15, K30}. The parent still has room (two keys), so no further split is needed and the root is unchanged.
Insert K25: it falls between K15 and K30, so it goes to the leaf {K15, K20}, giving {K15, K20, K25} — again an overflow. The leaf splits into {K15} and {K20, K25}, and K20 (the first key of the right leaf) is copied up into the parent {K15, K30}, giving it three keys {K15, K20, K30} — now the parent itself overflows.
The overflowing internal node splits: its middle key, K20, is moved (not copied) up to the root, leaving {K15} on the left and {K30} on the right as two separate internal nodes. The root, which held only K40, now holds {K20, K40} — still within capacity, so the process stops here.
The finished tree's leaves are {K10}, {K15}, {K20, K25}, {K30}, {K40}, {K50}, under internal nodes {K15} and {K30} (both children of the new root {K20, K40}) and {K50} (still on the right of the root, unchanged).
Two independent checks confirm this trace: (a) key count is conserved — the original tree held five keys (K10, K20, K30, K40, K50) and two were inserted (K15, K25), for seven keys total, matching the seven keys across the six finished leaves; and (b) every internal separator equals the first key reachable in its right subtree (K20 leads into {K20, K25}; K40 leads into {K40}), which is the defining invariant of a B+ tree.
Matching the four listed node configurations — (K30, K50), (K25, K30), (K20, K25), (K15, K20) — against the finished leaves {K10}, {K15}, {K20, K25}, {K30}, {K40}, {K50}, only (K20, K25) exists as an actual node. Exactly one of the four listed configurations is present in the tree.
