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: Determine number of data blocks directly

Total records = 25,000
Record size = 100 B
Block size = 1024 B

Maximum records per block = ⌊1024 / 100⌋ = 10

Total data blocks required:
25,000 / 10 = 2,500 blocks

---

Step 2: Determine index density

Primary index has one entry per data block.
So, total index entries = 2,500

Size of each index entry = 15 + 5 = 20 bytes

Index entries per block:
⌊1024 / 20⌋ = 51

---

Step 3: Determine index file height

Index blocks required:
⌈2500 / 51⌉ = 50 blocks

Since the index is searched using binary search, the number of block accesses needed is:

⌈log₂(50)⌉ = 6

---

Final Answer:

Number of block accesses required = 6