Multilevel indexing

Question

Database file consist 1250 records. Block can hold either 3 records or (10 keys, 11 pointers). The maximum number of levels of index required for sparse B⁺ tree index for database file are ______.

Please explain the solution. Ans is given 4

Comments

Order = P = number of pointers = 11

Maximum level when minimum pointers = ciel(P/2)=5  

In database number of block = 1250 /3= 417

so number of blocks at 1st levels  = 417 /5 = 84

number of blocks at 2nd levels  = 84 /5 =16

number of blocks at 3rd levels  = 16 /5 = 4

number of blocks at 4rth levels  = 4 /5 = 1

---

Ceil(p/2) will be 6.