In a B-tree of order 5, keys are inserted in this order: 7, 8, 1, 4, 13, 20,…
2010
In a B-tree of order 5, keys are inserted in this order: 7, 8, 1, 4, 13, 20, 2, 6, 5. Assuming order 5 means at most 5 children (and hence at most 4 keys) per node, how many keys are present in the root after all insertions?
Answer: B. 2 — ConceptIn a B-tree of order m, a node can have at most m children and therefore at most m − 1 keys. If insertion creates one extra key, the median key is…
- A.
1
- B.
2
- C.
3
- D.
4
Attempted by 38 students.
Show answer & explanation
Correct answer: B
Concept
In a B-tree of order m, a node can have at most m children and therefore at most m − 1 keys.
If insertion creates one extra key, the median key is promoted to the parent and the remaining keys are split into two nodes.
Application
Insert 7, 8, 1, and 4. The leaf becomes [1, 4, 7, 8], which is at the four-key limit.
Insert 13. The leaf [1, 4, 7, 8, 13] overflows, so promote the median 7. The root is [7], with children [1, 4] and [8, 13].
Insert 20. The right child becomes [8, 13, 20].
Insert 2 and then 6. The left child becomes [1, 2, 4, 6].
Insert 5. The left child [1, 2, 4, 5, 6] overflows, so promote the median 4. The root becomes [4, 7], with children [1, 2], [5, 6], and [8, 13, 20].
Cross-check
Each node is within the four-key limit, and a root with three children has two separator keys. Therefore, the root contains 2 keys.