The GATE Grind

GATE 2023 CS – Question 62

Databases · File Organization and Indexing (B and B+ Trees) · 2 marks · Numerical answer

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. 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 b blocks takes $\log_2 b$ 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 ______.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 6

Explanation

**Data file.** 25,000 records of 100 bytes, block size 1024 bytes, records not split across blocks: $\lfloor1024/100\rfloor=10$ records per block. Number of data blocks $=\dfrac{25000}{10}=2500$.

**Primary index.** One index entry per data block (sparse, ordered file): 2500 entries. Each entry = key (15 bytes) + block pointer (5 bytes) $=20$ bytes. Entries per index block $=\lfloor1024/20\rfloor=51$. Number of index blocks $=\left\lceil\dfrac{2500}{51}\right\rceil=50$.

**Binary search on the index** takes $\lceil\log_250\rceil=6$ block accesses in the worst case (the question asks for the accesses needed to identify the data block, so the final data block access is not counted).

Answer: **6**.

More File Organization and Indexing (B and B+ Trees) questions

All File Organization and Indexing (B and B+ Trees) questions →