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.

Computer Science & Information Technology

You might also like to view...

If you are not sure which clear property value to use, use the value ____________________.

Fill in the blank(s) with the appropriate word(s).

Computer Science & Information Technology

A(n) ________ is a data file that contains characters, such as letters, numbers, and symbols, including punctuation and spaces

Fill in the blank(s) with correct word

Computer Science & Information Technology

An image of an active window on your computer that can be pasted into a document is known as a(n) ________

Fill in the blank(s) with correct word

Computer Science & Information Technology

A PID is a ________ assigned to each running process

Fill in the blank(s) with correct word

Computer Science & Information Technology