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.
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 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 ______.
Tap to open full sizeFigure description
Two files side by side. The Index File (left) is a set of blocks, each holding rows of (Block Anchor Primary Key, Block Pointer). The Data File (right) is a set of blocks, each holding rows with columns Primary Key (15 Bytes) and Other Fields (85 Bytes). Each index row has a dot in its Block Pointer cell, with an arrow to the start of one data block, so each index entry points to one data block (the first record of the block is its anchor). Two index blocks are drawn with ellipses between them, and four data blocks are drawn with ellipses inside and between them.