1,100 views

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$ :(

I am getting total levels as 5..

and total nodes as 786..

is this the ans???
yes, level 5, but total nodes not correct.

What do u divide by in 2nd level??
since it is of order 8, each node should have 7 data, so i just divided 5500 by 7.... whats wrong in this approach? and what is the correct approach?

PS: I am comfortable with finding the number of levels, but cant actually figure out how to find the total nodes..
1st row from bottom has 5500 keys. order is max pointers a node can have so here it is 8. 7 is the key in each node.

5500/7 = 785 and remainder =5 => 786 nodes at bottom lvl where 785 node has 7 keys each and an extra node having 5 keys.

now these 786 nodes can be pointed by a x number of nodes which has 8 pointer each.

786/8 = 98 and remainder =2 => 99 nodes at 2nd  lvl from bottom where 98 node has 7 keys each and an extra node having 1 keys.

now these 99 nodes can be pointed by a x number of nodes which has 8 pointer each.

99/8 = 12 and remaider 3 => 13 nodes at 3rd  lvl from bottom where 12 node has 7 keys each and an extra node having 2 keys

now these 13 nodes can be pointed by a x number of nodes which has 8 pointer each.

13/8 = 1 and remainder 5 => 2  nodes at 3rd  lvl from bottom where 1 node has 7 keys each and an extra node having 4 keys

now these 2 pointers are stored at the root node having 1 key.

so total nodes = 786+99+13+2+1 = 901.
but why dividing by $8$ and not $7*8$ in 2nd level??

2nd level has $56$ pointers

rt??
Getting total levels as 5 and total nodes as 903. Is that right?
edited by

Do it for small value and draw it @srestha

lets say we have 10 keys and order is 3.

so keys in each node is 3-1=2.

now in leaf node we divide by 3 or 2 ? ....we divide by 2

level 1

10/2 = 5 nodes. (5 nodes each having 2 keys and 1 pointer pointing to its right node.)

level 2

now each of the 5 nodes can be pointed of by 1 pointer

1st node -> 2 value and 3 pointer

2nd node -> 1 value and 2 pointer.

so we need 5 pointers and each node can have  3 pointers

So we need 2 nodes

level 3

now each of these 2 nodes can be pointed of by 1 pointer

1st node -> 1 key 2 pointer. = root node

So leaf level is divided by (keys in each node) and non leaf by (child pointers of each node.)

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

It will help to understand why 8 and not 7.

by

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