edited by
1,412 views
3 votes
3 votes

The minimum number of nodes (both leaf and non-leaf) of $B^{+}$ tree index required for storing $5500$ keys and order of $B^{+}$ tree is $8$________________(order is max pointers a node can have)


 See here first level should be divide by $7$

$2nd$ levelshould divide by only $8$ or $7\times 8$

because, each $7$ pointer of 1st level has $8$ pointer in 2nd level.

Am I missing something??

But in ans they divided by only $8$ :(

edited by

2 Answers

Best answer
3 votes
3 votes

Sorry,Total nodes = 901

Ceil(5500/7) = ceil(785.71) = 786 --> Level 1

ceil(786/8) = ceil(98.25) = 99 --> Level 2

ceil(99/8) = ceil(12.375) = 13 -->Level 3

ceil(13/8) = ceil(1.625) = 2 --> Level 4

ceil(2/8) = ceil(0.25) = 1 -->  Level 5 

Minimum number of nodes = 786 + 99 +13 +2 +1

                                            = 901 

Please refer this : https://gateoverflow.in/163103/b-tree-with-sparse-dense-indexing 

It will help to understand why 8 and not 7.

selected by
0 votes
0 votes

As per Navathe “pleaf to denote the order for leaf nodes, which we define as being the maximum number of data pointers in a leaf node.”

Also see this for reference https://gateoverflow.in/269367/b-tree-self-doubt

As per question only one order is mentioned hence we take Pleaf also as 8 and therefore 8 keys are present in each leaf node.

Ceil(5500/8) = ceil(687.5) = 688 --> Level 4 (5500 divided by keys per node)

ceil(688/8) = ceil(86) = 86 --> Level 3 (here we are dividing by 8 and not 7 because block pointer are 8 which takes us to next level)

ceil(86/8) = ceil(10.75) = 11 -->Level 2

ceil(11/8) = ceil(1.375) = 2 --> Level 1

ceil(2/8) = ceil(0.25) = 1 -->  Level 0

Minimum number of nodes =  688 + 86 +11 +2 +1 = 788

Total nodes = 788                                       

Related questions

2 votes
2 votes
1 answer
1
0 votes
0 votes
0 answers
3
Abhishek Kumar Singh asked Dec 23, 2017
473 views
2 votes
2 votes
0 answers
4
Manu Thakur asked Oct 26, 2017
1,942 views
In the following question, How to know that at first level (base level) index entries will be recorded for a block or for each record?https://gateoverflow.in/2311/gate199...