Question

A particular Table in a relational database contains 100,000 Data Records/rows, each of which Data Record/row requires 200 bytes. A select statement returns all Data Records/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 Indexes on that attribute is used.
A. No Index (Heap File of Data Records)
B. A Static Hash Index (with no overflow buckets/Pages). Assume the cost of applying the hash function is H, negligible.

Answer 1

The correct question is;

A particular table in a relational database contains 100,000 rows, each of which requires

200 bytes of memory. Estimate the time in milliseconds to to insert a new row into the

table when each of the following indices on the related attribute is used. Assume a page

size of 4K bytes and a page access time of 20 ms.

a. No index (heap file)

b. A clustered, non-integrated B+ tree index, with no node splitting

required. Assume that each index entry occupies 100 bytes. Assume that the

index is 75% occupied and the actual data pages are 100% occupied. Assume

that all matching entries are in a single page.

Answer:

A) 20 ms

B) 120 ms

Explanation:

A) Append (at the end of file). Just one IO, i.e., 20 ms

B) Now, when we assume that each entry in the index occupies 100 bytes, then an index page can thus hold 40 entries. Due to the fact that the data file occupies 5000 pages, the leaf level of the tree must contain at least 5000/40 pages which is 125 pages.

So, the number of levels in the tree (assuming page 75% occupancy in the

index) is (log_30 (125)) + 1 = 3. Now, if we assume that the index is clustered and not integrated with the data file and all matching entries are in a single

page, then 4 I/O operations and 80ms are required to retrieve all matching

records. Two additional I/O operations are required to update the leaf page

of the index and the data page. Hence, the time to do the insertion is

120ms.