In a B+ tree, the requirement of at least half-full (50%) node occupancy is relaxed for which one of the following cases?
Topic-wise GATE CS PYQs with verified steps
GATE CSE 2024 Set 1 · Q21
Time
Select one answerSingle correct
Solution
Official answer: A) Only the root node
File Organization and IndexingIn a tree of order :
Every internal node (except the root) has at least children and at least keys.
Every leaf node (except when the root is the only node) contains at least (or ) key-pointer pairs.
The root node is an exception to the minimum occupancy rule: if it is not a leaf, it needs to have at least child pointers (and at least key), and if it is a leaf (i.e., the entire tree has records), it can contain as few as search key value (or even if the tree is empty).
Therefore, the requirement of at least half-full node occupancy is relaxed only for the root node.
Thus, (A) is the correct option.
Try the question first, then check your work.
Examiner trap
Consider the special node in a tree structure that can have as few as two children (if non-leaf) or even fewer keys without violating the tree properties when the total number of keys is small.
This File Organization and Indexing previous year question is Q21 of the GATE CSE 2024 Set 1 paper. Find more GATE CSE PYQs on File Organization and Indexing in Databases, or browse all GATE CSE PYQs.
Free diagnostic
Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related File Organization and Indexing PYQs now with no account.
An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.
File Organization and Indexing has 17 GATE CSE PYQs across 17 papers from 2011 to 2026. 5 of them are 1-mark MCQs like this one, and it is the only one in GATE CSE 2024 Set 1.
How GATE tests File Organization and IndexingIndependent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.