GATE CS 2021 Set 2 Q.31 (CS Q.21): File Organization, B-Trees and B+ Trees Indexing

A data file consisting of 1,50,000 student-records is stored on a hard disk with block size of 4096 bytes. The data file is sorted on the primary key RollNo. The size of a record pointer for this disk is 7 bytes. Each student-record has a candidate key attribute called ANum of size 12 bytes. Suppose an index file with records consisting of two fields, ANum value and the record pointer to the corresponding student record, is built and stored on the same disk. Assume that the records of data file and index file are not split across disk blocks. The number of blocks in the index file is ______.

Your answer

Official answer and solution

Official answer: 698
From: Official GATE 2021 answer key

Solution

Compute the size of each index record, determine how many records fit in one disk block without splitting, and compute total index blocks needed for all records.

The data file contains $1,50,000$ student records and is sorted on RollNo. An index is constructed on ANum, which is a candidate key (non-ordering key). Therefore, this is a secondary index (dense index), meaning there is exactly one index entry for each record in the data file:

\text{Total index records} = 1,50,000

Each index entry contains two fields:

Candidate key value ANum: $12\text{ bytes}$
Record pointer: $7\text{ bytes}$

\text{Size of one index record} = 12 + 7 = 19\text{ bytes}

Given a disk block size of $4096\text{ bytes}$ and that records cannot be split across blocks, the blocking factor $B_{\text{index}}$ (number of index records per block) is:

B_{\text{index}} = \left\lfloor \frac{4096}{19} \right\rfloor = \lfloor 215.5789 \rfloor = 215\text{ records/block}

The number of disk blocks required to store all $1,50,000$ index entries is:

\text{Number of blocks} = \left\lceil \frac{1,50,000}{215} \right\rceil = \lceil 697.674 \rceil = 698\text{ blocks}

Final answer

698

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2021 Computer Science and Information Technology - Session 2 (CS2)
Question: 31 of 65, printed as CS Q.21
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source