14.20

Suppose there is a relation \(r(A,B,C)\), with a B+-tree index with search key \((A, B)\).

  1. What is the worst-case cost of finding records satisfying \(10 < A < 50\) using this index, in terms of the number of records retrieved \(n_1\) and the height \(h\) of the tree?

  2. What is the worst-case cost of finding records satisfying \(10 < A < 50 \wedge 5 < B < 10\) using this index, in terms of the number of records \(n_2\) that satify the selection, as well as \(n_1\) and \(h\) defined above?

  3. Under what conditions on \(n_1\) and \(n_2\) would the index be an efficient way of finding records satisfying \(10 < A < 50 \wedge 5 < B < 10\)?

  1. What is the worst-case cost of finding records satisfying \(10 < A < 50\) using this index, in terms of the number of records retrieved \(n_1\) and the height \(h\) of the tree?

\(O(h + n_1)\)

  1. What is the worst-case cost of finding records satisfying \(10 < A < 50 \wedge 5 < B < 10\) using this index, in terms of the number of records \(n_2\) that satify the selection, as well as \(n_1\) and \(h\) defined above?

\(O(h + n_1)\)

  1. Under what conditions on \(n_1\) and \(n_2\) would the index be an efficient way of finding records satisfying \(10 < A < 50 \wedge 5 < B < 10\)?

When \(n_2 = n_1\).