Skip to content
GATEiit

GATE CSE 2023 Q62: Block accesses with a sparse primary index and binary search

Question

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.

Primary index: index file blocks hold entries (block anchor primary key, block pointer); each pointer points to a block of the data file, whose records have a 15-byte primary key and 85 bytes of other fields
Tap the figure to enlarge

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 bb blocks takes ⌈log⁡2b⌉\lceil \log_2 b \rceil 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 _______.

Try it: numerical answer: type the value

Numerical answer. No negative marking.
Show answer and explanation

Answer: 6 (official GATE 2023 final answer key)

Concept used: A sparse primary index has one entry per data block; binary search runs over the index blocks.

First step: Find the number of data blocks (⌊1024/100⌋=10\lfloor 1024/100 \rfloor = 10 records per block), which is the number of index entries.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2023 CS question paper and final answer key, organised by IIT Kanpur. Question paper · Answer key

More Databases PYQs

PracticePractise Databases questions →Full paperAll GATE CSE 2023 questions →