A B-Tree used as an index for a large database table has four levels including…
2005
A B-Tree used as an index for a large database table has four levels including the root node. If a new key is inserted in this index, then the maximum number of nodes that could be newly created in the process are:
- A.
5
- B.
4
- C.
3
- D.
2
Attempted by 112 students.
Show answer & explanation
Correct answer: A
Answer: 5
Key idea: In the worst case the inserted key causes a split at the leaf and those splits propagate up through every level to the root. Each split creates a new sibling node; when the root splits it also requires creation of a new root node.
Level 4 (leaf): leaf is full and splits, creating 1 new node.
Level 3 (parent of leaf): split propagates and creates 1 new node.
Level 2 (next internal level): split creates 1 new node.
Level 1 (root): splitting the root produces a new sibling node and also a new root node, i.e., 2 new nodes.
Total newly created nodes = 1 + 1 + 1 + 2 = 5.