Consider a database of fixed-length records, stored as an ordered file. The database has records, with each record being bytes, of which the primary key occupies 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.
Suppose the block size of the file system is bytes, and a pointer to a block occupies 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 blocks takes 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 _____________.
View worked solution
Answer: 6
To find the number of block accesses required to identify the target data block, we first determine the structure of the data and index files:
- Data File Blocks:
- Number of records per data block = records.
- Total data blocks () = blocks.
- Index File Blocks:
- Since a primary index is a sparse index, it contains one entry per data block. Thus, there are index entries.
- Size of each index entry = bytes.
- Number of index entries per block = entries.
- Total blocks in the index file () = blocks.
The worst-case number of block accesses to search the index file using binary search is:
Free practice · Your answers on this page are not saved.