GATE2025_CS1_Q21

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?

Note: This is a Multiple Select Question (MSQ). One or more options may be correct.

✅ Final Answer:

The correct options are (B) and (D).

🔹 Short Answer:

Inserting the value 23 into the B+ tree causes a cascading split. First, the rightmost leaf node {20, 21, 22} is full and must split. This pushes a key up to the root. Since the root {6, 12, 19} is also full, it must also split. This root split creates a new, higher root level, thereby increasing the tree's height. Thus, at least one node splits, and the height increases.

🔸 Long Answer:

Let's analyze the insertion step-by-step.

1. B+ Tree Properties

• A node can store at most 3 key values, so the maximum number of keys, m = 3.
• The order of the tree, p = m + 1 = 4.
• Maximum children for an internal node is p = 4.
• Minimum children for a non-root internal node is ceil(p/2) = 2.
• Minimum keys for a non-root node is ceil(p/2) - 1 = 1.

2. Insertion of 23

Step 2.1: Find the target leaf node.
We start at the root {6, 12, 19}. Since 23 is greater than 19, we traverse to the rightmost child, which is the leaf node {20, 21, 22}.

Step 2.2: Insert into the leaf and split.
The leaf node {20, 21, 22} is full. Inserting 23 results in a temporary node {20, 21, 22, 23}, which overflows. We must split it into two nodes. For B+ Trees, a copy of the first key of the new right leaf is promoted.

• New Left Leaf: {20, 21}
• New Right Leaf: {22, 23}
• Key to be promoted: A copy of 22

Step 2.3: Insert into the parent (root) and split.
The key 22 is pushed up to the root node {6, 12, 19}. The root is also full. Inserting 22 results in a temporary node {6, 12, 19, 22}, which also overflows. The root must split.

• The middle key 12 is promoted to become the new root.
• New Left Internal Node: {6}
• New Right Internal Node: {19, 22}

3. Final Tree Structure & Evaluation

The splitting of the original root node results in a new level being added to the tree. The height increases from 1 to 2. The final tree is structured as follows:

Now, let's re-evaluate the given statements:

• (A) None of the nodes will split.
  This is FALSE. Both a leaf node and the root node split.
• (B) At least one node will split and redistribute.
  This is TRUE. As shown, two nodes split to accommodate the new key.
• (C) The total number of nodes will remain same.
  This is FALSE. The tree started with 5 nodes. After insertion, it has 8 nodes (1 new root, 2 internal nodes, 5 leaf nodes). The count increased.
• (D) The height of the tree will increase.
  This is TRUE. The original height was 1 (edges from root to leaf). After the root split, the new height is 2.

Bibliography:
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. MIT Press. (Chapter 18: B-Trees).
- Garcia-Molina, H., Ullman, J. D., & Widom, J. (2008). Database Systems: The Complete Book. Pearson. (Chapter on Tree-Structured Indexing).

Ask your doubts in comment form our GURUJEE will reply ASAP, click notify me button so that you get notified on reply.