edited by
18,473 views
66 votes
66 votes

A B-Tree used as an index for a large database table has four levels including the root node. If a new key is inserted in this index, then the maximum number of nodes that could be newly created in the process are

  1. $5$
  2. $4$
  3. $3$
  4. $2$
edited by

8 Answers

Best answer
96 votes
96 votes

Suppose all nodes are completely full means every node has $n-1$ keys. tree has $4$ levels if a new key is inserted then at every level there will be created a new node. and in worst case root node will also be broken into two parts. and we have $4$ levels so, answer should be 5 because tree will be increased with one more level.

Correct Answer: $A$

edited by
58 votes
58 votes
For those who are finding it difficult to understand for the 1st time:

All levels and all nodes are completely filled with keys.
Another key came.
It went down to leaf.
Overflow happened at the leaf.
The leaf is broken into two parts and one key moved to the upper level.
Again overflow. That node is broken into two parts and one key moved to the upper level.
Same thing will happen till we reach the root.
The root itself is broken into two parts + we have a new root.

So in all 'n' levels, we got one extra node and we got a new root too.
So total n+1 extra nodes.  Hence answer is 4+1 = 5.
17 votes
17 votes
A

5 is the correct answer. To find maximum no of nodes newly created, assume that all nodes are full. Adding one more to leaf will split the leaf at level 4 (+1) , the middle element moves up and splits the parent node at level 3 (+2), similiarly a split at level 2(+3) , and now at root node a split (+4) and its middle element forms a new root node(+5). Now the B tree has 5 Levels with 5 new nodes created
Answer:

Related questions