3,935 views
0 votes
0 votes

Maximum height of a B+ tree of order m with n key values is (With Derivation), the answer is known Logceil(m/2) N

I tried deriving but had some trouble, could someone assist with the derivation or derivation process ?

1 Answer

0 votes
0 votes

for height to be maximum each node should have minimum elements :

for root node its : key =1 child_pointer=2

for other nodes = key=ceil(n/2)-1  child pointer=ceil(n/2)

height                           key                                                 child pointer

0                                  1                                                                      2

1                            2*ceil(p/2)-1                                            2*ceil(p/2)

2                           2*(ceil(p/2)-1)(ceil(p/2)                2*ceil(p/2)(ceil(p/2))

3                           2*(ceil(p/2)-1)ceil(p/2)2                          2*ceil(p/2)3

.

.

h                 1*2*(ceil(p/2)-1)ceil(p/2)h-1

----------------------------------------------------------------------------------------------     1+(2*ceil(p/2)-1)+   2*(ceil(p/2)-1)(ceil(p/2) +............................. 2* ceil(p/2)h-1 ceil(p/2)-1      = n

-----------------------------------------------------------------------------------------------

=1+ 2*ceil(p/2)-1 ( ceil(p/2)h-1)/(ceil(p/2)-1)

=1+( 2 * (ceil(p/2)h-1) )=n

=2*(ceil(p/2)h-1 =n

= h = log ceil(p/2) ((n+1)/2)

which can be considered as logceil(p/2)(n) answer only when n is very large .

edited by

Related questions

0 votes
0 votes
1 answer
1
Vishnathan asked Aug 24, 2018
8,183 views
3 votes
3 votes
2 answers
3
Proton asked Mar 21, 2015
6,003 views
I think answer is 7 ,if not then pls explain .
0 votes
0 votes
0 answers
4
bts1jimin asked Jan 9, 2019
375 views
Can anyone suggest me any useful source from where I can read b+ tree insertion and deletion?