Self doubt

Question

Consider a B+ tree in which the maximum number of keys in a Internal node is 5 and maximum number of keys in a leaf node is 4. What is the minimum number of keys in any non-root node?

Comments

Minimum number of keys in any non-root internal node = 2

Answer 1

In case of B+ trees

Use the Formula  [(ceil of (p/2)-1),p-1], to calculate the Minimum and maximum number keys in an internal node.

Here P is the Order of the Internal Nodes.

 

 

Answer 2

it's impossible.in B+ tree order is the max no of keys present in leaf node and max child ptrs present in non-leaf nodes. so according to the q order is 4 and as order 4 max keys that can be present in any non-leaf node is 3 ..but your q says its 5 which is not possible.. it has to be less than 4

Answer 3

Answer is 2

Given:

1. B+ tree 
2. Max no. of keys in the internal node is 5
3. Max no. of keys in the leaf node is 4

Solution:

We know that the max child pointer in the internal node of the B+ tree

= max no of keys in internal node + 1

= 5 + 1  i.e  6

Hence the max order of B+ tree internal node = 6

 

 

Now for a given internal node of the B+ tree, the min order of any internal node

=  ceil (order / 2)

= ceil (6/2)

= 3

Now, if the min order is 3, then min number of keys would be 3-1 = 2