B+ tree

Question

Database file consists 1250 records.Block can hold either 3 record or (10 key,11 pointer ) The max number of level of index required for dense B+ tree index for daatabase file are _____________________

Answer 1

it is dense indexing.. so index will be created for every record

p=11

max number of nodes when all the nodes are filled with minimum number of keys

1. at leaf level number of blocks=$\left \lceil \frac{1250}{5} \right \rceil$=250

at leaves minimum occupancy=$\left \lceil \frac{p}{2} \right \rceil-1$

as the rightmost pointer points to its right sibling so we don't count it

for all other nodes min occupancy=$\left \lceil \frac{p}{2} \right \rceil$=6

2. for pre-leaf level, number of blocks=$\left \lceil \frac{250}{6} \right \rceil$=42

3. for next level number of blocks=$\left \lceil \frac{42}{6} \right \rceil$=7

4. next level, number of nodes=$\left \lceil \frac{7}{6} \right \rceil$=2

5. 1 node for root

there are 5 levels

Comments

@abhishekmehta4u pls check whether my answer is correct or not

Answer 2

Database file consists 1250 records.Block can hold either 3 record or (10 key,11 pointer ). The max number of level of index required for dense B+ tree index.

To get max number of levels in B+ tree, we will assume that each node is half full and will contain 5 keys and 6 pointers.

1st level = 1 node, 1 key, 2 pointers, ( Root node is not forced to obey this rule of min keys and pointers)
2nd level = 2 nodes, 10 keys, 12 pointers.
3rd level = 12 nodes, 60 keys, 72 pointers
4th level = 72 nodes, 360 keys, 432 pointers
5th level = 432 nodes, 2160 keys, 2592 pointers

So, as you can see if we need minimum 2160 keys then our B+ Tree can be of 5 levels, but keys are less than 2160 and more than 360, hence B+ tree will be of levels 4 only.

Hence, correct answer is 4.

Comments

As keys are less than 2160 but greater than 360, dont we need one more level to fit in all the (1250-360=)890 keys?? So shudnt the answer be 5 levels as dense indexing is used?

---

@pranab ray

I've one doubt. why are u dividing by 6
here p=11

so any non-root node should have min number of keys=ceil(p/2)-1=ceil(11/2)-1=5
so every non root node should have minimum occupancy of 5

---

@aditi19

yes it should be divide by 5.