6.7k views

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 | 6.7k views

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$
by Boss (33.9k points)
edited by
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.

by Active (4k points)
+1
good job

thank you
+1
Perfect explanation.
+1
nice explanation.
+1
This should be the best answer, instead of giving one line formula explanations like this are far far batter.
Thanks buddy !
0
Good Explanation.
0
That's the way to think. Great. Getting a correct answer and getting it correctly are two different things sometimes. Nicely explained. It'd be better if this was put in the GO pdfs.

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

by Loyal (7.3k points)

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

by Active (2k points)
+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)

by Loyal (8k points)
0
can u show me the resources where they mentioned this method ??
0
@PujaMishra Ankur Gupta OS notes (Refer last pages).
0

@Aghori can u mention link here. which notes!

0

Why do we need to learn the formula when we know -

The order of internal nodes is the maximum number of tree pointers in each node, and the order of leaf nodes is the maximum number of data items that can be stored in it

u can make your own formula by this

+1 vote

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

by Loyal (6.3k points)
by Boss (10.2k points)

This can be perceived by below diagram.

by Boss (10.2k points)