Question

Consider a B+ Tree where the maximum number of key values in each leaf node is 2 and the maximum number of pointers in each non-leaf node is 3. Let the content of the B+ Tree be as shown in the figure.

Which of the following options denotes the key value(s) stored in the root node after inserting a key value 3 in the given B+ Tree?

• A. 5
• B. 8
• C. 3 and 5
• D. 3, 5 and 8

Hint:

First find which leaf 3 falls into using the \(\le\) rule on the root separators, then check the leaf split, and finally check if the root itself now has too many pointers and must split too.

Answer 1

The Correct Option is A

Step 1: Read off the tree structure and the search rule.
The leaf capacity is 2 keys and the non-leaf capacity is 3 pointers, so every internal node can hold at most 2 keys.
The current leaves are [1, 5], [7, 8] and [9, 12], joined left to right, and the root holds the two separator keys 5 and 8.
Reading the pointers against the leaves shows the rule used here: the first pointer covers keys \(\le 5\), the middle pointer covers keys in \((5, 8]\), and the last pointer covers keys \(> 8\).

Step 2: Find the leaf that receives the new key.
We need to insert 3. Since \(3 \le 5\), it goes down the first pointer into the leaf [1, 5].
Inserting 3 into that leaf gives [1, 3, 5], which now has 3 keys, one more than the leaf limit of 2.

Step 3: Split the overflowing leaf.
With 3 keys to share out, the left leaf keeps the first \(\lceil 3/2 \rceil = 2\) keys, [1, 3], and the right leaf keeps what remains, [5].
The largest key of the left leaf, 3, is copied up into the parent as the new separator between these two leaves.

Step 4: Check whether the root also overflows.
Before the insert, the root [5, 8] already pointed to 3 children, the maximum allowed for a non-leaf node with pointer limit 3.
The leaf split adds one more child, so the root would need to hold 3 keys, [3, 5, 8], and point to 4 children, which breaks the pointer limit.
So the root itself has to split as well.

Step 5: Split the root.
For an internal (non-leaf) node split, the middle key is pushed up alone to form a new root; it is not left behind in either child, unlike a leaf split.
Of the three keys [3, 5, 8], the middle one is 5, so 5 moves up by itself.
The left internal node keeps key 3, pointing at leaves [1, 3] and [5]; the right internal node keeps key 8, pointing at leaves [7, 8] and [9, 12].

Final Answer:
The new root now holds only the single key 5, which matches option (A).\[ \boxed{\text{Root} = \{5\}} \]