Consider an employee table with columns age and sal and we are interested in ana

Question

Consider an employee table with columns age and sal and 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.

Count the worst case number of IOs of each of these queries for (1) heap file storage, (2) sorted file storage, (3) heap+tree, (4) heap+hash, and (5) clustered file. Let be the number of data pages, be the number of records per page, be the number of records returned by a range query, and be the fanout of the tree index.

Example Heap File:

Query IOS Algoriothm Notes Scans Point Range Insert Delete

Explanation / Answer

Cost Model:

B is the number of data pages with R records

D is the average time for read/ write a disk page

Note: F is F-ary search

Scan Point Range Insert Delete Heap BD 0.5BD BD 2D Search+D Sorted BD Dlog2(B) Dlog2(B) Search+BD Search+BD Heap+Tree BD Dlog2(B) Dlog2(B)+#matches Search+BD Search+BD Hash+Tree BD*1.25 D BD*1.25 2D Search+D Clustered 1.5BD DlogF(1.5B) DlogF(1.5B)+matching pages Search+D Search+D

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---