binary search
a. The database first compares the search value to an entry in the middle of the index.
b. If the search value is less than the entry value, the search value is in the first half of the index. If not, the search value is in the second half.
c. The database now compares the search value to the entry in the middle of the selected half, to narrow the search to one quarter of the index.
d. The database continues in this manner until it finds the index block containing the search value.