IAE Academy

GATE 2024 CS1 Q.21: solution and answer

GATE 2024 · CS1Q.21 · 1 mark · MCQ

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

See the question in the paper

Answer and solution

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)

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

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

  3. An internal root needs only 2 children, however large is.

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

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

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

More Indexing questions