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

I think it should be just 4 levels.

Since it's dense indexed, there are 1250 blocks.

Each block must point to 6 other blocks to maximize it.

Level 1: ceil(1250/6) = 209

Level 2: ceil(209/6) = 35

Level 3: ceil(35/6) = 6

Level 4: ceil(6/6) = 1

You're right that the rule does not apply on the root node, but that doesn't mean you add another node which does not follow the rule. We must index it to an extent where there's only one node pointing to rest. So the asnwer should be 4.

---

I think you're answer is correct, and not only my answer but concept is also wrong, because unlike B tree, In B+ Tree we should count record nodes at leaf level only, right?

---

Yes.

But why is your concept wrong? I was just trying to understand you answer and the only problem I think is that you started with the first node having only 1 key, 2 pointer.

Can you let me know?

And if this were a B-tree how do we visualize it?

---

in B Tree, keys are everywhere either at the leaf node or internal node, while in B+ tree, record pointers are at the leaf level only, but if you notice, in my solution i am adding keys at each level. my solution is partially correct if it was B tree.

---

I slightly modified my solution.

---

question also says 1 block can hold 3 records so total ceil(1250/3) blocks we have. which is 417

so in b+ tree we have to arrange only 417 blocks why you considering 1250?

---

Because it's dense indexed. In dense index we have a block anchor for every record unlike sparse.

---

k thank u i didnt notice that in question

---

no of record=1250 and every block can hold 3 record so

at leaf level of B+ tree no of blocks=1250/3=417blocks=417 pointers required

in question given max no of level so we have to take ceil(p/2)=6;

417/6=70blocks----- level 1

70/6=12 blocks---level 2

12/6=2 ----level3

2/6=1---level4

4 levels required

---

Why #manu00 u

assume that each node is half full and will contain 5 keys and 6 pointers...

Plz explain is it necessary for max

---

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.