GATE CS 2023 Q.62: File Organization, B-Trees and B+ Trees Indexing

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 scheme showing an Index File of blocks containing (Block Anchor Primary Key, Block Pointer) entries pointing to the first record of each block in an ordered Data File of (Primary Key 15 Bytes, Other Fields 85 Bytes) records.

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 $\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 the record is _______.

Your answer

Official answer and solution

Official answer: 6
From: Official GATE 2023 answer key

Solution

Determine the blocking factors of data and index files, then compute worst-case binary search block accesses.

Data File:
- Block size = $1024\text{ bytes}$ , Record size = $100\text{ bytes}$ .
- Unspanned blocking factor: $\text{Bfr}_{\text{data}} = \lfloor 1024 / 100 \rfloor = 10\text{ records/block}$ .
- Total data blocks: $b_{\text{data}} = \lceil 25000 / 10 \rceil = 2500\text{ blocks}$ .
Primary Index File:
- A primary index has one index entry per data block (sparse index): $2500$ index entries.
- Each index entry contains a primary key ( $15\text{ bytes}$ ) and a block pointer ( $5\text{ bytes}$ ): $\text{entry size} = 15 + 5 = 20\text{ bytes}$ .
- Index blocking factor: $\text{Bfr}_{\text{index}} = \lfloor 1024 / 20 \rfloor = 51\text{ entries/block}$ .
- Total index blocks: $b_{\text{index}} = \lceil 2500 / 51 \rceil = \lceil 49.019 \rceil = 50\text{ blocks}$ .
Binary Search Accesses:
- Worst-case block accesses to locate the entry in the index file: $\text{Accesses} = \lceil \log_2(b_{\text{index}}) \rceil = \lceil \log_2(50) \rceil = \lceil 5.644 \rceil = 6\text{ block accesses}$

Final answer

Common trap

Adding 1 for accessing the data block, whereas the question explicitly asks for block accesses required to 'identify the block in the data file' (i.e., searching within the index file).

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

Source

Paper: GATE 2023 Computer Science and Information Technology (CS)
Question: 62 of 65
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