and total nodes as 786..

is this the ans???

Dark Mode

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

0

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.

3

edited
May 18, 2019
by Satbir

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

0

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

0 votes

As per Navathe “*p*leaf 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