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
In a B+ tree, the requirement of at least half-full (50%) node occupancy is relaxed for which one of the following cases?
Only the root node
All leaf nodes
All internal nodes
Only the leftmost leaf node
ANSWER
The half-full requirement is relaxed only for the root node, so the answer is (A).
Official answer: ASource: Official answer key, GATE 2024 CS1 (IISc Bengaluru)
In a B+ tree of order , every node other than the root must be at least half full. An internal node holds at least children, and a leaf holds at least keys.
The root is the exception. A root that is a leaf may hold as few as 1 key, which is needed while the tree holds very few records.
An internal root needs only 2 children, however large is.
So the occupancy rule is relaxed for the root alone. Options (B) and (C) are wrong: leaves and internal nodes that are not the root must stay at least half full, and splits, borrowing and merges maintain this.
Option (D) is wrong: no leaf is exempt because of its position. The leftmost leaf follows the same minimum as every other non-root leaf.
Hence the 50% occupancy requirement is relaxed only for the root node, which is option (A).
KEY IDEA
Every non-root node of a B+ tree must be at least half full, and only the root is exempt: it can be a leaf with a single key, or an internal node with just 2 children.
WATCH OUT FOR
Thinking that leaf nodes, or the leftmost leaf, can be under-full because they sit at an edge of the tree. Only the root is exempt, wherever a node sits.
From the GATE 2024 CS1 paper. Every question of this paper · Download the full paper · All 9 Indexing questions, with notes