Question Details

In a B+ - tree where each node can hold at most four key values, a root to leaf path consists of the following nodes:
A = (49, 77, 83, –), B = (7, 19, 33, 44), C = (20*, 22*, 25*, 26*)
The *-marked keys signify that these are data entries in a leaf. Assume that a pointer between keys k1​ and k2​ points to a subtree containing keys in [k1,k2], and that when a leaf is created, the smallest key in it is copied up into A. A record with key value 23 is inserted into the B+ - tree. The smallest key value in the parent of the leaf that contains 25* is ______.

Show Answer
Correct Answer
33

Solution :

The correct answer is 33.

Step-by-Step Explanation:

1. Initial State of the B+ Tree:
We are given the following path from root to leaf:
- Root node A = (49, 77, 83, –)
- Internal node B = (7, 19, 33, 44)
- Leaf node C = (20*, 22*, 25*, 26*)
Note that leaf node C is currently full because it contains four key values, which is the maximum limit per node.

2. Inserting Key 23:
When a record with key value 23 is inserted, it must be placed in leaf node C because 20 < 23 < 26. This temporarily creates an overfull leaf node containing 5 keys: (20*, 22*, 23*, 25*, 26*).

3. Splitting Leaf Node C:
To resolve the overflow, leaf node C is split into two leaf nodes:
- Left leaf C1 = (20*, 22*, 23*)
- Right leaf C2 = (25*, 26*) (which contains 25*)
Following B+ tree insertion rules, the smallest key of the new right leaf C2 (which is 25) is copied up to the parent internal node B.

4. Splitting Internal Node B:
With the entry 25 copied up, the parent node B now contains 5 keys: (7, 19, 25, 33, 44). Since this exceeds the maximum limit of 4 keys, internal node B must split:
- The middle key (25) is pushed up to the root node A.
- The remaining keys are split into two internal nodes:
  • Left internal node B1 = (7, 19)
  • Right internal node B2 = (33, 44)

5. Identifying the Parent of Leaf C2:
The pointer corresponding to the range [25, 33] resides in the right split internal node B2 = (33, 44). Therefore, the leaf node containing 25* (which is C2) becomes a child of B2.
The keys present in the parent node B2 are (33, 44), making the smallest key value in this parent node 33.

Transparent Access on Mindyard

Built for Learners & Educators Alike

Completely free for students. Educators & coaching institutes get 2 months free Pro trial to create tests.

FREE FOR STUDENTS

Practice & Learn Free for Students

Access unlimited practice questions, detailed step-by-step solutions, and exam study materials — completely free for students.

  • Unlimited mock tests & question bank practice
  • Full access to curated study library & formula notes
  • 100% free for students • No credit card required
2 MONTHS FREE TRIAL

Educators & Coaching Institutes

Create and conduct professional online assessments with AI question generation, tab proctoring, and comprehensive batch management.

  • AI question uploader & rapid test generator
  • Anti-cheating tab proctoring & performance reports
  • Full Pro access free for 60 days • No upfront commitment
Discover more resources

You may also like

Mock Tests

View All
  • GATE
  • beginner
  • 3 hours
  • civil engineering

Prepare for GATE 2026 Civil Engineering with the latest question papers, previous year papers, detailed solutions, syllabus, exam pattern, preparation tips, mock tests, and subject-wise study material. Download GATE 2026 CE question papers with solutions in PDF format and boost your preparation for top engineering institutes and PSU recruitment.

  • GATE
  • beginner
  • 3 hours
  • electronics and communication engineering

Prepare effectively for GATE 2026 Electronics & Communication Engineering (EC) with this comprehensive Question Paper with Solutions. This resource includes detailed explanations, concept-wise solutions, previous year paper analysis, and exam-oriented practice to help aspirants strengthen core subjects like Electronic Devices, Analog Circuits, Digital Circuits, Signals & Systems, Network Theory, Control Systems, Electromagnetics, Communications, and more. Perfect for revision, self-assessment, and boosting your GATE 2026 EC preparation strategy.

Ask AI Tutor
5 left
Q1 View Question & Options
AI Tutor is solving this question...
Reading question context & options...
Ask your own doubt or choose a quick prompt: