IAE Academy

GATE 2023 CS Q.62: solution and answer

GATE 2023 · CSQ.62 · 2 marks · NAT

Consider a database of fixed-length records, stored as an ordered file. The database has 25,000 records, with each record being 100 bytes, of which the primary key occupies 15 bytes. The data file is block-aligned in that each data record is fully contained within a block. The database is indexed by a primary index file, which is also stored as a block-aligned ordered file. The figure below depicts this indexing scheme.

Suppose the block size of the file system is 1024 bytes, and a pointer to a block occupies 5 bytes. The system uses binary search on the index file to search for a record with a given key. You may assume that a binary search on an index file of blocks takes block accesses in the worst case.

Given a key, the number of block accesses required to identify the block in the data file that may contain a record with the key, in the worst case, is ______.

GATE 2023 CS question 62: Two files side by side.Tap to open full size
Figure from the GATE 2023 CS paper. It is part of the question.
Figure description

Two files side by side. The Index File (left) is a set of blocks, each holding rows of (Block Anchor Primary Key, Block Pointer). The Data File (right) is a set of blocks, each holding rows with columns Primary Key (15 Bytes) and Other Fields (85 Bytes). Each index row has a dot in its Block Pointer cell, with an arrow to the start of one data block, so each index entry points to one data block (the first record of the block is its anchor). Two index blocks are drawn with ellipses between them, and four data blocks are drawn with ellipses inside and between them.

Answer and solution

ANSWER

6 block accesses: a binary search over the 50 index blocks takes accesses, and the index entry it finds already names the data block.

Official answer: 6Source: Official answer key, GATE 2023 CS (IIT Kanpur)

  1. Records per data block . The file is block-aligned, so no record spans two blocks.

  2. Data blocks .

  3. The primary index is sparse: one entry (block anchor primary key, block pointer) per data block, as the figure shows. So the index has entries.

  4. Index entry size bytes. The index file is also block-aligned, so entries per index block .

  5. Index blocks .

  6. Binary search on the index file takes block accesses in the worst case, since .

  7. The question asks only for the accesses needed to IDENTIFY the data block that may hold the key. The index entry found by the binary search already carries that block's pointer, so no data block has to be read. The data-block read that would follow (to fetch the record) is not counted here.

  8. Worst-case block accesses .

KEY IDEA

A sparse primary index holds one (anchor key, block pointer) entry per data block. Count data blocks, then index blocks, then apply the given worst-case binary-search cost to the index file alone.

WATCH OUT FOR

Adding 1 for reading the data block (giving 7). The question asks for the accesses needed to identify the block that may contain the record, not to fetch the record, so the data-block read is not counted. Other slips are building one index entry per record (a dense index, 25,000 entries) instead of one per data block, and using entries per block without the floor.

From the GATE 2023 CS paper. Every question of this paper · Download the full paper · All 9 Indexing questions, with notes

More Indexing questions