Consider the following \(B^{+}\) tree with 5 nodes, in which a node can store at most 3 key values. The value 23 is now inserted in the \(B^{+}\) tree. Which of the following option(s) is/are CORRECT?
Answer
(B), (D)
Explanation
23 is larger than every key, so it belongs in the rightmost leaf (20, 21, 22). That leaf is full, and so are all the other leaves, so no key can be moved to a neighbour: the leaf must split, for example into (20, 21) and (22, 23), sending the separator 22 up to the root.
The root (6, 12, 19) is also full, so it splits too and a new root is created above the two halves. The tree grows from 2 levels to 3 and from 5 nodes to 8.
- (A) False: the leaf and the root both split.
- (B) True: each full node splits and its keys are shared between the two halves.
- (C) False: three nodes are added (a new leaf, the second half of the old root, and the new root).
- (D) True: the new root adds a level.
Answer: B, D