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?

  1. A.

    Only the root node

  2. B.

    All leaf nodes

  3. C.

    All internal nodes

  4. 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.

Explore the full course: Gate Guidance By Sanchit Sir