edited by
32,708 views
56 votes
56 votes

Consider a $B^+$-tree in which the maximum number of keys in a node is $5$. What is the minimum number of keys in any non-root node?

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

8 Answers

Best answer
77 votes
77 votes
Answer: B

Order = $5$+$1$ = $6$
Minimum children in a non root node = $\lceil$ $\frac{Order}{2}$ $\rceil$ = $\lceil$ $\frac{6}{2}$ $\rceil$ = $3$
Keys = Minimum children in a non root node - $1$ = $2$
edited by
96 votes
96 votes
In a b+ tree if a non-root node can be a leaf-node or a non-leaf-node:

case 1) when a non-root, leaf node is full and a new key is inserted in it:

a) the initial keys in the row + the newly inserted key is arranged in asc/desc order

b) the medium key is copied to an upward node without the record pointer

c) the medium key is retained in the leaf node with the record pointer

d) the keys in the leaf node are split in half and moved to two separate nodes

here there are maximum 5 keys, so when an additional key comes, the medium key is copied upwards, and a total of 6 keys are split in two nodes having 3 keys each.

case 2) when a non-root, non-leaf node is full and a new key is inserted in it:

a) the initial keys in the row + the newly inserted key is arranged in asc/desc order

b) the medium key is moved to an upward node

c) the medium key is removed from the current node

d) the keys in the current node are split in half and moved to two separate nodes

here there are maximum 5 keys, so when an additional key comes, the medium key is moved upwards, and a total of 5 remaining keys are split in two nodes having 2 keys and 3 keys respectively.

 

SO the minimum number of keys in a non-root leaf node is 3 and the minimum number of keys in a non-root non-leaf node is 2.

SO the minimum number of keys in a non-root node is 2.

Hence answer is (B)
5 votes
5 votes

An important property that helps in keeping the $B / B^+$ trees balanced is that they enforce at least 50% space utilization.

B-tree nodes are kept between 50 and 100 percent full

-- Navathe 6th Edition, page 647, line number 3.

This means if a node can accommodate max $p$ children, it must accommodate at least $\frac{p}{2}$ children at any time. (This is not applicable to the root, however.)

Of course, fractions are resolved by taking ceil, because if the $B / B^+$ tree wants us to have minimum $3.6$ children, we will keep $4$ children and not $3$. So, $\frac{p}{2}$ is actually $\left \lceil \frac{p}{2} \right \rceil$.

 

Now, we know that the number of keys is always one less than the number of children.

So minimum number of keys = $\left \lceil \frac{p}{2} \right \rceil-1$.


Now, coming to the question.

Max keys = 5. Hence, max children it can have = 6. (p is 6)

Minimum keys it can have = $\left \lceil \frac{p}{2} \right \rceil-1$.

= $\left \lceil \frac{6}{2} \right \rceil-1$.

= $2$

 

Option B

4 votes
4 votes

Ans: B

order= maximum no of children = maximum number of keys + 1

                                                  = 5+1 = 6

degree, t= order/2 = 6/2= 3

max key = (2t-1) = 2*3-1=5

min key = t-1=3-1=2

Answer:

Related questions

12 votes
12 votes
5 answers
1
go_editor asked Sep 30, 2014
6,503 views
$25$ persons are in a room. $15$ of them play hockey, $17$ of them play football and $10$ of them play both hockey and football. Then the number of persons playing neithe...
7 votes
7 votes
1 answer
2
go_editor asked Sep 30, 2014
3,881 views
Choose the most appropriate word from the options given below to complete the following sentence:If we manage to __________ our natural resources, we would leave a better...
41 votes
41 votes
2 answers
4