GATE CS 2008 Q70 — File Organization and Indexing (B and B+ Trees)

To find the number of blocks at each level of the multi-level secondary index, we proceed as follows:

1. Identify the Index Type: Since a secondary index is built on a key field (which is not the ordering field of the file), it must be a dense index. This means there is one index entry for every record in the data file.
   Number of records = $16384$
   Number of first-level index entries = $16384$
2. Calculate Index Entry Size ($R_i$): $$R_i = \text{Key size} + \text{Block pointer size} = 6\text{ bytes} + 10\text{ bytes} = 16\text{ bytes}$$
3. Calculate Index Blocking Factor ($Bfr_i$): $$Bfr_i = \left\lfloor \frac{\text{Block size}}{R_i} \right\rfloor = \left\lfloor \frac{1024}{16} \right\rfloor = 64\text{ entries per block}$$
4. Number of First-Level Blocks ($b_1$): $$b_1 = \left\lceil \frac{\text{Number of first-level entries}}{Bfr_i} \right\rceil = \left\lceil \frac{16384}{64} \right\rceil = 256\text{ blocks}$$
5. Number of Second-Level Blocks ($b_2$): The second level of a multi-level index is a sparse index containing one entry for each block of the first level.
   Number of second-level index entries = $256$ $$b_2 = \left\lceil \frac{256}{Bfr_i} \right\rceil = \left\lceil \frac{256}{64} \right\rceil = 4\text{ blocks}$$

Thus, the number of first-level and second-level blocks are 256 and 4 respectively.