MadeEasy Test Series: Databases - B Tree

Question

What is the minimum levels of B+ tree index required for 5000 keys and order of B+ tree node (P) is 10. (Assume P is the max pointer possible to store in B+ tree node)

 

My answer was 3.

With: Keys <= (Internal Order)^levels * (Leaf Order)

i.e., 10^3 * 9 = 9000 >= 5000 .. So 3 levels req. But given answer is 4.

Comments

level 0---9 level 1---9x10 level 2---9x10x10 level 3---9x10x10x10.. hence 4 levels

---

remember what they are asking., not the height but level . level wil be 4 and height will be 3

---

As complexity for search key is which shows.  $\lceil{log_pn}\rceil$        tte height so can we use it here
$\lceil{log_95000}\rceil$ =4

Answer 1

Mx no of keys in B+ tree of order 10 height H is :

10^(H+1) - 1 = 5000
10^(H+1) = 5001
H + 1= 4
H = 3
if we consider root at level 1 than level =height +1
so Number of levels = 4
 

 

other way:

 order is 10 so each node can have at max 9 keys
at 1st level: key:9
2nd level: 10*9
3rd 10*10*9
4th level: 10 *10 *10*9

so Number of level = 4

Comments

 Digvijay Pandey sir how  level =height +1 ??? i think it is not correct.

level=depth+1

---

https://stackoverflow.com/questions/2603692/what-is-the-difference-between-tree-depth-and-height

---

I am not sure, i should laugh or not.

when you are condidering level 1 as height of root

formula must be

$k = m^{h}-1$

where m is order of B+ tree and h is height of B+ tree.

now you will get h=4

---

in 2^nd method you are caliculating for b tree and not b+ tree