Question

A database has 25,000 fixed-length records of 100 bytes (primary key 15 bytes). The data file is block-aligned so each record is fully contained within a block. The file is indexed by a primary index file, also block-aligned and ordered. Block size is 1024 bytes and a block pointer is 5 bytes. Each index entry stores the block’s anchor key (15 bytes) and a pointer (5 bytes). Binary search on an index file of \(b\) blocks needs \(\lceil \log_2 b \rceil\) block accesses in the worst case. Given a key, the number of block accesses required to identify the data file block that may contain the record, in the worst case, is ____________.

Hint:

For primary indexes, the number of index entries equals the number of data blocks. Compute index blocks from entry size and block size, then apply \(\lceil \log_2(\text{\# index blocks}) \rceil\) for worst-case binary search cost.

Answer 1

Step 1: Records per data block
Block size \(=1024\) B, record size \(=100\) B \(\Rightarrow\) records per block \(=\left\lfloor \frac{1024}{100}\right\rfloor = 10\).
Number of data blocks \(=\left\lceil \frac{25{,}000}{10}\right\rceil = 2{,}500\).
Step 2: Primary index entries and blocks
Each index entry size \(= 15 + 5 = 20\) bytes.
Entries per index block \(=\left\lfloor \frac{1024}{20} \right\rfloor = 51\).
Number of index blocks \(= \left\lceil \frac{2{,}500}{51} \right\rceil = 50\).
Step 3: Binary search cost on index file
Worst-case index block accesses \(=\left\lceil \log_2 50 \right\rceil = 6\).
Thus, to identify the candidate data block via the primary index, the system needs \(6\) block reads in the worst case.
\[ \boxed{6} \]