14.20

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

a. 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?

b. 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?

c. 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$?

---

a. 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)$

b. 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)$

c. 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$.