The GATE Grind

GATE 2025 CS (CS1) – Question 21

Databases · File Organization and Indexing (B and B+ Trees) · 1 mark · Multiple select

Consider the following $B^+$ tree with 5 nodes, in which a node can store at most 3 key values. The value 23 is now inserted in the $B^+$ tree. Which of the following options(s) is/are CORRECT?

root [6, 12, 19] with four leaves [1, 4, 3], [7, 9, 10], [13, 15, 17], [20, 21, 22].
  1. None of the nodes will split.
  2. At least one node will split and redistribute.
  3. The total number of nodes will remain same.
  4. The height of the tree will increase.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) At least one node will split and redistribute.; (D) The height of the tree will increase.

Explanation

23 goes into the full leaf [20,21,22], which splits and pushes a key up to the root. The root [6,12,19] is already full, so it also splits and a new root is created. The height increases and the node count grows.