The GATE Grind

GATE 2026 DA – Question 41

Database Management and Warehousing · File organization and indexing · 2 marks · Multiple choice

Consider a B+ Tree where the maximum number of key values in each leaf node is 2 and the maximum number of pointers in each non-leaf node is 3. Let the content of the B+ Tree be as shown in the figure.

Which of the following options denotes the key value(s) stored in the root node after inserting a key value 3 in the given B+ Tree?

A B+ tree. The root holds the keys 5 and 8. Its three children are leaves holding 1 and 5, 7 and 8, and 9 and 12, joined in a chain.
  1. 5
  2. 8
  3. 3 and 5
  4. 3, 5 and 8

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) 5

Explanation

In this tree a separator key is the largest key of the subtree to its left (the left leaf holds 1 and 5 under the key 5). The key 3 goes into the first leaf, which becomes 1, 3, 5 and overflows. It splits into the leaves (1, 3) and (5), and the separator 3 moves up. The root would then have the keys 3, 5 and 8 with four pointers, which is too many (the maximum is 3 pointers), so the root splits as well. The middle key 5 moves up into a new root, with one new node holding the key 3 over the leaves (1, 3) and (5), and another holding the key 8 over (7, 8) and (9, 12). The new root holds only the key 5.