GATE CS 2021 Set 2 Q21 — File Organization and Indexing (B and B+ Trees)

To find the number of blocks required for the index file, we need to determine the type of index, the size of each index record, and the number of index records that can fit in a single block.

1. Determine the Type of Index

• The data file is sorted on the primary key $\textrm{RollNo}$.
• The index is built on $\textrm{ANum}$, which is a candidate key (non-ordering key).
• An index on a non-ordering key is a Secondary Index. Since it is a secondary index, it must be a dense index (i.e., there is one index entry for every record in the data file).
• Therefore, the total number of index records ($N$) = $1,50,000$.

2. Calculate the Index Record Size

Each index record consists of the candidate key $\textrm{ANum}$ and a record pointer:

3. Calculate the Blocking Factor of the Index File

Since the records cannot be split across disk blocks (unspanned organization), the number of index records per block ($B_{fr}$) is:

4. Calculate the Number of Blocks for the Index File

The total number of blocks required is:

Thus, the number of blocks in the index file is 698.