and total nodes as 786..

is this the ans???

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

0

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..

PS: I am comfortable with finding the number of levels, but cant actually figure out how to find the total nodes..

3

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.

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.

0

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.)

2 votes

Best answer

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.