In a B+ tree, the requirement of at least half-full (50%) node occupancy is…
2024
In a B+ tree, the requirement of at least half-full (50%) node occupancy is relaxed for which one of the following cases?
- A.
Only the root node
- B.
All leaf nodes
- C.
All internal nodes
- D.
Only the leftmost leaf node
Attempted by 343 students.
Show answer & explanation
Correct answer: A
Answer: Only the root node
Explanation:
Minimum-occupancy rule: Except for the root, internal nodes must have at least about half the maximum number of children (typically ceil(m/2) children for order m), and leaf nodes must have at least about half the maximum number of entries.
Root exception: The root node is allowed to be less than half full. If the root is internal it may have as few as two children; if the root is the only node (a leaf), it may contain between one and the maximum number of entries.
Conclusion: Because only the root is permitted to violate the half-full requirement, the correct answer is that the rule is relaxed only for the root node.
A video solution is available for this question — log in and enroll to watch it.