MADE EASY TEST SERIES

Question

What is the maximum number of records that can be indexed for a B⁺ tree of 4 levels with order 10 and root at level 1?

Answer 1

If we take order of internal node = order of Leaf Node = 10.

Then, max. keys = 10-1= 9.

Children At Level 1 = 10

Children At Level 2 = 10*10

Children At Level 3 = 10*10*10

Total Nodes At Level 4 = 10*10*10

Total Keys = Total Record Pointers = Total Records Can be pointed out = 9*10*10*10=9000.

Answer 2

Order = maximum pointers per node = 10. So key =9

In B+ trees, data records to be indexed are always stored at the leaf level. So,

 

Level	Max Node	Max ptr	Max key
1	1	10	9
2	10	$10^{2}$	10$\times$9
3	$10^{2}$	$10^{3}$	$10^{2}\times$9
4	$10^{3}$	$10^{4}$	$10^{3}\times$9

So maximum number of records that can be indexed for a B⁺ tree =$10^{3}\times$9=9000

Comments

Actually, 9000 was given as the answer. This should be the solution I think:

Level 1= 1 node

Level 2= 10 nodes

Level 3= 10*10= 100 nodes

Level 4= 100*10=1000 nodes

Each node of level 4 shall have 9 record pointers.

Hence, 1000*9= 9000