retagged by
1,351 views
2 votes
2 votes

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

  • (m-1)h-1
  • (m-1)h-1+1
  • Mh-1
  • Mh+1+1
retagged by

1 Answer

Best answer
5 votes
5 votes

Lets consider a smaller B-tree of order 4, with only 1 node.

Maximum number of keys that may be present in this tree is 3.

Now, if we put h=1 in option C, we get 3. No other option satisfies.

But, the thing is, I did the above verification to see if they are considering the root at height 0 or at height 1. It seems they have set the options considering the root at height 1. Now, lets derive the formula.

Since, order of the B-tree is 'm', each node can have maximum (m-1) keys.

Number of keys at height 1 = (m-1)

Number of keys at height 2 = m * (m-1) {Because 'm' block pointers of a node at height 1 gives rise to 'm' nodes at height 2}

Number of keys at height 3 = m2 * (m-1)

Likewise, Number of keys at height 'h' = mh-1 * (m-1)

Maximum number of keys, n = (m-1) + m(m-1) + m2(m-1) + ........ + mh-1(m-1) = (m-1)[1 + m + m2 + ........ + mh-1] = (m-1)$\frac{1*(m^{h}-1)}{m-1}$ {Sum of GP formula, where common ratio is m}

$\therefore$ n = mh-1

selected by

No related questions found