Exercise 18: Analyze Different Storage & Indexing Strategies

Consider an employee table with columns age and sal. We are interested in analyzing the performance of the following five types of queries.

1. Scans : fetch all records in the table.
2. Point : fetch one record using the primary key.
3. Range : fetch all records where the age is greater than some constant.
4. Insert: insert a new record.
5. Delete: delete a record using the primary key.

For each of the storage and indexing strategy below, sketch the most efficient algorithm to process each of the five queries, and count the worst case number of IOs (big-O notation) in each case.

1. heap file storage
2. sorted file storage
3. heap storage + tree index
4. heap storage + hash index
5. clustered file storage

Let B be the number of data pages, R be the number of records per page, S be the number of records returned by a range query, and F be the fanout of the tree index.