GATE CSE 2021 | Set 2 | Question: 21

Question

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 $\textrm{RollNo}$. The size of a record pointer for this disk is $7$ bytes. Each student-record has a candidate key attribute called $\textrm{ANum}$ of size $12$ bytes. Suppose an index file with records consisting of two fields, $\textrm{ANum}$ value and the record pointer 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 ________

Comments

check bottom most answer

---

@Vansh_Dhamecha you first need to calculate blocking factor, and then calculate no. of index block required 

---

first understand what type of index file it is i.e primary index,clustterd,secondary ??

  the data is sorted in the basis of Roll_no which is primary ..BUT BUT INDEX IS BASED on ANum (which key also)

now understand secondary index definition: search key in index file is unordered attribute of data file 

in this two sub cases: 1.Secondary index on non-key

                                   2.secondary index in key 

according to question it follows SI on key:

the implementation of SI on key is dense because (each attribute is unique(due to CK) so we need to put every record key in index file also )

so index file also we need to store 1,50,000 records and with size of 19 B(12B+7B) .now ,,block size=4096

      no.of records for block= 4096/19=215.57 (Assume that the records of data file and index file are not split across disk blocks) so 215 records for each block 

so total no.of blocks required for 1,50,000= 1,50000/215=697.67 

  .i.e Blocks required is =698

Answer 1

ANS = 698 .

Index is being built on attribute “ANum” which is Candidate Key, but Given that file is Sorted on Primary Key “Roll No”.

This indicates that The Index must a Secondary Index, (data records not being physically ordered as per the index making a dense record necessary) so “THERE SHOULD EXIST AN INDEX RECORD FOR EVERY RECORD of Original ‘Student Table’ ”.

=> Also this Line: “Assume that Records of data file and index file are not split across disc blocks”.

This indicates UNSPANNED STRATEGY.

With This Knowledge, let’s see the Data given.

→ Record Size in Index $= 12 + 7 = 19 \text{ B}$ (‘ANum’ key size + Record pointer Size), and Block Size $= 4096 \text{ B}$

→ So number of Index records in 1 Block $= \left \lfloor \frac{4096}{19} \right \rfloor= 215$ records in 1 block (Remember again, unspanned strategy).

→ So number of blocks in the Index file $= \dfrac{\text{Total Number of records}}{\text{Records per block}} = \left \lceil \dfrac{1,50,000}{215}\right \rceil = 698.$

(Recall that this is Secondary Index)

Comments

@nishant.singhal.cs When a question asks for the "number of blocks in the index file," one calculates the blocks needed to store the initial, single layer of index entries, which are often the leaf nodes in a larger structure. Calculation of the additional levels (internal nodes and the root) is done if the question explicitly asks for a "multi-level index," or the "total storage cost" of the entire index structure.

---

Why are we not going for 2nd level and so on? Like 698 blocks can further be indexed into ceil(698/215)  blocks etc?

---

they haven't mention anything related to multilevel indexing

Answer 2

📦 Step-by-step calculation:

1. How many index records fit in one block?

⌊4096/19⌋=⌊215.5789⌋=215 records per block

2. Total number of index records?

Since each student record has a unique ANum, we need 150,000 index records.

3. Number of blocks required for index file:

⌈150000/215⌉=⌈697.674⌉=698 blocks