A table has 100,000 rows and each row occupies 200 bytes. The table is stored on a disk which has 4k bytes per page. Compute the maximum (worst case) cost (number of I/O operations) of doing an equality search on the primary key assuming the following access paths. Make your reasoning clear - a number without an explanation gets no credit.

Question

(a) The data file is unsorted and has no index.
(b) The data file is sorted on the primary key and has no index.
(c) There is an unclustered static hash index whose search key is the primary key. Assume all buckets are stored on disk and that each bucket has one overflow page.
(d) There is an unclustered B+ tree index whose search key is the primary key. Assume that each entry in the tree occupies 20 bytes and the entire tree resides on the disk.

Answer 1

(a) The data file is unsorted and has no index.
Solution
The data file has (105 200)/(4 103) pages = 5000 pages
In the worst case the entire file has to be searched costing 5000 I/O operations.
(b) The data file is sorted on the primary key and has no index.
Solution
Use binary search. Cost = log25000. Hence worst case is 13 I/O operations.
(c) There is an unclustered static hash index whose search key is the primary key. Assume all buckets are stored on disk and that each bucket has one overflow page.
Solution
Cost of hash is 0; cost of searching bucket = 2 I/O operations; cost of retrieving row = 1 I/O operation; total = 3 I/O operations.
(d) There is an unclustered B+ tree index whose search key is the primary key. Assume that each entry in the tree occupies 20 bytes and the entire tree resides on the disk.
Solution
(4 103)/20 = 200 maximum entries per page; 100 minimum entries per page (worst case)
105/102 = 1000 leaf pages
Rounding log1001000 up to the next integer (2) we get that the number of levels of the tree is 3. Hence 3 I/O operations are necessary to search the tree and an additional I/O operation is necessary to fetch the row.