$Min$ $children$ $=$ $\left \lceil \frac{p}{2} \right \rceil -1$

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

46 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$
- $2$
- $3$
- $4$

59 votes

Best answer

65 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)

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)

3 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

2 votes

Maximum number of keys in B+ tree -> leaf node having 5 keys

order of leaf = number of key+record pointer value

order of non leaf = number of block pointers

If not given in question explicitly then

O (leaf) = O(non leaf)

since O(leaf) = 5

max number of block pointer in nonleaf = 5

therefore minimum number of keys will be in non leaf = ceil(5/2)-1 = 3-1 = **2**

**Answer B**

2 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**

1 vote

Given maximum number of keys in any node is 5 ...

So Order of non-leaf node(maximum number of children) is 5+1 = 6

Order of leaf node(maximum number of keys) = 5 which is given in question...

Minimum number of keys possible in any non-leaf node = **[ ceil (order_of_nonleaf_node) / 2 ] - 1** = 2

Minimum number of keys possible in any leaf node = ** [ ceil (order_of_leaf_node) / 2 ]** = 3

So minimum number of nodes possible in the B+ tree = **min (2,3) = 2**

(we have ignored the special case of root as per question which can even have 1 key, EX :when our data file has only one record)