Problem 2

Consider a B+ tree with root, two additional levels of internal nodes, and leaf nodes (4 nodes on paths from root down to and including leaf) that is a dense index on some attribute a of relation r. Assume a is UNIQUE, i.e. no two tuples of r have the same value of attribute a. Suppose n = 15 and each internal node, including the root, has 10 children and assume each leaf node has 10 values. Assume each node is on its own disk block. Assume each data block in r has 5 tuples (with different values of a).

1. How many different values of a does r have?

2. What is the numerical value of b_r (the number of data blocks r occupies)?

3. Consider execution of the query SELECT * FROM r WHERE a = foo How long will it take in the worst case to execute the query using a sequential scan of the whole file (in terms of the block access (seek + rotational latency) time, t_s, and the block transfer time, t_T ) ?

4. How long will it take in the worst case to execute the query using the index (in terms of t_s and t_T ) ?

5. Under what conditions on the ratio of t_s to t_T will using the index be faster (in the worst case) ?