UGC NET CSE | December 2010 | Part 2 | Question: 21

Question

What is the maximum number of nodes in a B-tree of order $10$ of depth $3$ (root at depth $0$) ?

• A. $111$
• B. $999$
• C. $9999$
• D. None of the above

Answer 1

Answer: C

At level 0, max keys can be 9

At level 1, max keys can be 10*9 = 90 (10 nodes containing 9 keys each)

At level 2, max keys can be 10*10*9 = 900

At level 3, max keys can be 10*10*10*9 = 9000

Total = 9000 + 900 + 90 + 9 = 9999

Comments

They have asked maximum number of nodes!!!!!!  Not kyes

---

First here it is not clear whether the order is used for keys or block pointer?

in question, it is asked the number of nodes possible not keys?

---

then it would be 1111 nodes.

Answer 2

The answer is asked about number of nodes. so the formula for finding the maximum number of  nodes (n)
n=(m^(d+1) -1)/m-1
So, number of nodes = (10^4  - 1) / 9  =  1111

Answer is d.