UGC NET CSE | December 2012 | Part 2 | Question: 34

Question

The maximum number of keys stored in a B-tree of order $m$ and depth $d$ is

• A. $m^{d +1}-1$
• B. $\frac{m^{d+1}-1}{m-1}$
• C. $(m-1)(m^{d+1}-1)$
• D. $\frac{m^d-1}{m-1}$

Answer 1

Options are wrong I think so...

m$^{(d+1)}$-1 is the ans ...

Height	No.of keys
0	m-1
1	m$^1$ * (m-1)
2	m$^2$ * (m-1)
d	m$^d$ * (m-1)

Sum = m-1 + m$^1$* (m-1) + m$^2$ * (m-1) ....+ m$^d$ * (m-1)

= (m-1) ( 1+ m$^2$ + m$^2$ + ... + m$^d$)

= (m-1) [ $\frac{(m^{(d+1)} -1)}{(m-1)}$ ]

= m$^{(d+1)}$ - 1

Comments

it is better to type answer or else you change the image orientation

---

I'll  type too...

---

@Papesh Sir,Please can there be a diagrammatic representation of the above answer?

Answer 2

B tree is order m and deapth d . so it will have blocks = (1+m+m^2 + m^3+ ................. + m^d)

which is a Geometrical progression ; So blocks will be = m^(d+1)-1/(m-1)

and in order m B tree each block will have (m-1) keys maximally .

so total no of keys possible = (m-1)*(m^(d+1)-1)
                                          --------------------------------  = (m^(d+1)-1)
                                            (m-1)

so option A is the right one but (d+1) is the power of m .