made easy mock

Question

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 maximum pointers a node can have)

 

am getting 4681

Comments

i am getting as 643. what is the actual answer?

---

answer is 901

---

actually i was counting from the root filling root with maximum capacity which is incorrect as it will not always ensure all leaves will be at same level in b+ tree.

Answer 1

so we have 5500 keys of database so these 5500 keys need to be stored in the leaves of b+ trees.(as all <k,ptr> pairs are stored in the leaves of B+ tree).

here B+ tree order is 8 so we have 7 key pointer pairs available at each leaf node. As we have to count minimum number of B+tree nodes we will fill leaf nodes and non leaf nodes with maximum capacity as possible.

so for 5500 keys:

1.at lowest level:$\left \lceil 5500/7 \right \rceil$ = 786

{actually here 785 nodes are full and the last one is 71% full which is valid as a nodes at least should have 4 pointers (or 3 <key ptr> pairs in minimum)}

 

2.for 786 nodes now we will need pointers in upper level so  $\left \lceil 786/8\right \rceil$ = 99 nodes.

{here observe that 786/8 is actually 98.25 so we have 98 nodes are full and 99th node is 25% full which is not allowed as it will undergo underflow .so we will distribute keys between 98th node and 99th node so that they both will be valid now}

 

3. for 99 nodes again we need $\left \lceil 99/8\right \rceil$ =13

 

4. for 13 nodes we need $\left \lceil 13/8\right \rceil$ =2

 

5. for the 2 nodes we need 1 node which is root which can have minimum 2 pointers =1

 

so totally we have 786+99+13+3=901 minimum number of nodes

 

Comments

@newdreamz a1-z0

I've one doubt

at pre-leaf level why are u dividing by 8?

for B+ tree any non-root node will have max p-1 keys

here every node can have max 7 keys

---

Order of leaf node in b+ tree is maxm no of keys so it divide by 7.

Order of nonleaf in b+ tree is maxm no of block pointer so it divide by 8

---

thanks @abhishekmehta4u
that cleared my doubt for max occupancy
I've more doubt too

given order p, what will be the min occupancy at leaf and non-leaf node of B+ tree?

Answer 2

901 is right.

Comments

And record pointer of leaf is same as block pointer of other node, but without last pointer

This doesn't makes sense. Say if the index is dense. Then all key pointers of leaves will point to individual records not blocks

When the index is sparse then key pointers in leaves will point to blocks containing records

---

Is leaf level min key $\left \lceil \frac{p}{2} \right \rceil-1$ or $\left \lceil \frac{p}{2} \right \rceil??$

nptel  pdf telling , it is $\left \lceil \frac{p}{2} \right \rceil$

---

https://gateoverflow.in/219422/indexing#c312941

see this 

for all nodes min number of keys=$\left \lceil \frac{p}{2} \right \rceil-1$