retagged by
3,766 views
7 votes
7 votes
What is minimum levels of B+ tree index required for 5000 keys and order of B+ tree node (P) is 10. (Assume P is max pointer possible to store in B+ tree node)

Answer Given : 4
retagged by

4 Answers

11 votes
11 votes
Since the maximum pointer is 10 the number of keys that could be stored is 9

At level 1 => 9 keys

At level 2 =>9*10 keys =90

At level 3 =>9*10*10=900

since we still need to store the keys we move for next level

At level 4 => 9*10*10*10=9000

so we need atleast 4 levels to store 5000 keys
1 votes
1 votes

[Edit]

since each internal node can point to 10 nodes,

at each level, we have $10^h$ nodes, where h is height of tree. now since all keys are accommodated at the leaf nodes, and each leaf node can hold 9 keys, 

$10^h \times 9 \geq 5000$

$ h \geq 2.7$

hence height of B+tree would be 3, and number of levels would be 0,1,2,3 = 4

Answer is 4

PS: thanks for pointing out the mistkae

edited by
1 votes
1 votes
Now in B+ trees since all keys are present in leaves ;
so starting from leaves ;

at first level = 5000 / 9 = 556( P is number of block pointers so number of keys = 9)
at second level = ceil (556/10 ) =56 ; (since p =10 so we can have 10 block  pointers and keys = 9 )
at 3rd level = ceil (56/10) = 6
at fourth level 6/10 = 1;
so  four levels

Please let me know if this is the correct method.
0 votes
0 votes

if order is O ,level is L and keys = n then

O L - 1 = n 

so 10 L -1 = 5000 , 10 L = 5001 ,10 L = 10 4  

because 10 3 = 1000 which is less so we have to take 4

So level = 4

Related questions

0 votes
0 votes
0 answers
1
0 votes
0 votes
3 answers
2
Na462 asked Feb 2, 2019
2,043 views
0 votes
0 votes
0 answers
3
bts1jimin asked Jan 9, 2019
375 views
Can anyone suggest me any useful source from where I can read b+ tree insertion and deletion?
0 votes
0 votes
1 answer
4
Markzuck asked Dec 18, 2018
466 views
By default take ROOT at level 1 or 0?and if asked for B tree then take all the levels but for B+ records only at leaf so only leaf level keys right?