Question

Assume a sorted relation has 40 GB (file size), block size is 4KB, each block stores 40 records. Assume the index B+ tree has entries for each record, and the fanout of the node for B+ tree is 100. Select with an equality condition on the attribute, search key of index. Assume the disk seek cost is 5 milliseconds, and block transfer cost is 1 milliseconds. Also assume if the selection is a non key attribute, there are 100 matching records (duplicates).

For the following selection operations, consider which selection algorithm applies for each case, and find the number of block transfers, the number of seeks, and the cost, respectively:

1. Suppose that B+ tree index search key is the attribute used to sort the relation, and is also a key attribute.

2. Suppose that the index search key is not the attribute used to sort the relation, but is a key attribute. Analyze its difference from 1.

3. Suppose that the index search key is the attribute used to sort the relation, but is a nonkey attribute. Analyze its difference from 1.

4. Suppose that the index search key is not the attribute used to sort the relation, and is a nonkey attribute. Analyze its difference from 1.

5. How about using linear search? Analyze the selection on key or non-key attribute, respectively.

Answer 1

Size of 1 record = 8 + 4 = 12

Let the order be N.

No. of index values per block = N - 1

(N - 1) 12 + 4 = 512

12N - 12 + 4 = 512

16N = 1009

N = 43.33