First we can understand the terms given in the question:
- Uniform blocking factor $= 8$
This is the no. of records which can be held in a data block.
This information is required for DENSE index which is mandatory when the index is unclustered - data records not ordered by the search key (there is an index entry for each record) as compared to fully sparse (which has an index entry for each data block). Since in the question we do not have any information about "record pointer size" we can assume that the index is sparse. (Solution considering dense index is given at end)
- Block size $= 1\; \text{KB}$
This is the size of data block (file block containing records) as well as index block (file block containing index entries). Since file size is given as 1 giga bytes, we get no. of data blocks $ = \frac{1 \; \text{GB}}{1\; \text{KB}} = 1 \; \text{M} = 2^{20}$
- Block referencing pointer size $= 32 \; \text{bits} = 4 \; \text{B}$
This is the pointer size required to point to a block.
- The referencing capability (fanout ratio) per block of index storage may be considered to be $32.$
This means that an index block can refer to $32$ blocks (either data or index blocks). i.e., even though we have $1024$ bytes in a block, and each block pointer size is $4$ bytes, it can refer to only $32$ blocks. This might be due to large search key size which must be present for each index entry.
Now, coming to the solution:
No. of entries in first level index (which indexes to the data blocks) (in case of page tables in virtual memory, this will be the total no. of entries in last level page table) $=$ no. of data blocks (assuming sparse index) $ = 2^{20}$
No. of index blocks in level $1 = \frac{2^{20}}{32} = 2^{15}$ as each index block can refer to $32$ blocks (given fanout) which means size of level $1$ index $ = 2^{15} \times 1\; \text{KB} = 32 \; \text{MB}$
Since the fanout is $32,$ no. of index blocks in second level $ = \dfrac{2^{15}}{32} = 2^{10}$.
Size of second level index $ = 2^{10} \times 1\; \text{KB} = 1 \; \text{MB}$
No. of index blocks in third level $ = \frac{2^{10}}{32} = 32$.
Size of third level index $ = 32 \times 1\; \text{KB} = 32 \text{ KB}$
No. of index blocks in fourth level $ = \frac{32}{32} = 1$ and it occupies $1\; \text{KB}.$ Since only $1$ index block is there we do not need further level of indexing.
Searching starts in the last level (this will be level $1$ page table in case of virtual memory in OS).
Master Index -- not sure exactly what this means but I assume this is the complete index whose size will be $32 \text{ MB} + 1 \text{ MB} + 32 \text{ KB} + 1 \text{ KB}= 33.033 \text{ MB}$
Now assuming dense index.
Block pointer size $= 32 \text{ bits}$. Since, we have $8$ records in a block, we need at least $3$ more extra bits for a record pointer. So, we need to assume $5$ bytes for a record pointer. As fanout is given in the question it is not changing when the record pointer size changes. If fanout was not given, we could have calculated it as $\frac{\text{block size}}{\text{search_key_size}+\text{record pointer size}}$
Here, we need an index entry for each record. So, we need $ = \frac{1 \; \text{GB}}{1\; \text{KB}} \times 8 = 8 \; \text{M} = 2^{23}$ entries in first level index.
No. of index blocks in first level $ = \frac{2^{23}}{32} = 2^{18}$
Size of first level index $ = 2^{18} \times 1 \text{ KB} = 256 \text{MB}$
No. of index blocks in second level $ = \frac{2^{18}}{32} = 2^{13}$
Size of second level index $ = 2^{13} \times 1 \text{ KB} = 8 \text{MB}$
No. of index blocks in third level $ = \frac{2^{13}}{32} = 2^{8}$
Size of third level index $ = 2^{8} \times 1 \text{ KB} = 256 \text{KB}$
No. of index blocks in fourth level $ = \frac{2^{8}}{32} = 8$
Size of fourth level index $ = 8 \times 1 \text{ KB} = 8 \text{KB}$
No. of index blocks in fifth level $ = \lceil \frac{8}{32} \rceil = 1$
Size of fifth level index $ = 1 \times 1 \text{ KB} = 1\text{ KB}$
Master Index size $ = 256 \text{ MB} + 8 \text{ MB} + 256 \text{ KB} + 8 \text{ KB} + 1 \text{ KB} = 264.265 \text{ MB}$