A particular table in a relational database contains 100,000 rows, each of which requires 200 bytes of memory. A SELECT statement returns all rows in the table that satisfy an equality search on an attribute. Estimate the time in milliseconds to complete the query when each of the following indices on that attribute is used. Make realistic estimates for page size, disk access time, and so forth.

a. No index (heap ?le)
b. A static hash index (with no over?ow pages)
c. A clustered, unintegrated B+ tree index

a. Assume a page size of 4K bytes and a page access time of 20ms. The data ?le occupies 5000 pages and all pages will have to be scanned. Hence, the query will require 100 sec.
b. 20ms.
c. If we assume that each entry in the index occupies 100 bytes then an index page can hold 40 entries. Since the data ?le occupies 5000 pages, the leaf level of the tree must contain at least 5000/40, or 125 pages. Then the number of levels in the tree (assuming page 75% occupancy in the index) is log30125 + 1 = 3. Assume that the index is clustered, not integrated with the data ?le and that all matching entries are in a single page, 4 I/O operations and 80ms are required to retrieve all matching records.