B-Tree: Counting number of keys.

Question

Let T be a B-tree of order m and height h. if n is the number of key elements in T then the maximum value of n is ? 

I'm getting $m^{h+1}-1$, Am I correct? 

Comments

yes.same as like binary tree with order 2($2^{(h+1)-1}$) here it is 3

---

[m^(h+1)-1]/m-1

Answer 1

Root(height 1) --  1 nodes m pointer m-1 keys

(height 2) --  m nodes m*m pointer m*(m-1)
.
.
.
(height h) --  m^(h-1) nodes m^h pointer   m^h*(m-1)
 

total keys = (m-1) + m*(m-1) + m*m(m-1) +....+ m^h*(m-1)

               =   (m-1){ 1 + m + m² + m³ +.... m^h}

               = m^h-1

Comments

Maximum Nodes in B/B+ tree=1+m+m^2...

=  (m^h+1 -1)/m-1

Maximum keys  in B tree =m^h+1  -1

Maximum keys in B+ tree  =m^h  *(m-1)

Answer 2

yes u r right

Answer 3

[m^(h+1)-1]/m-1

Comments

u r wrong,take some example like m=3 and h=2 then max no of keys in a B-tree is 26 but not 13.

---

yeah, I didnt notice that its asking for keys and not blockptr

..

---

(2m^(h+1) )-1

if u found anything invalid ,please update me too
Explanation:

order=m

maximum no of child in each node=2m

maximum no of keys in each node=2m-1

 

height=0

key=2m-1 child=2m

height1=

total  no of key=2m(2m-1)

height =3

keys=2m(2m(2m(2m-1)))

 

height h=(2m)^h*(2m-1)

 

 

it is forming GP

2m-1(1+2m+2m^2+......2m^(h))

=2m^(h+1)-1