Made Easy Test Series:Database-Indexing

Question

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

Comments

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?

---

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

Answer 1

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.

Answer 2

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