In the ADDRESS table, the CITY column is defined as the primary key. A user has entered the following SELECT statement:
SELECT * FROM address WHERE city=?Athens?
The database system searches the ADDRESS table for the data record that has the value Athens in the CITY column.
1. The database system begins the search at the root level of the B* tree. It compares the value Athens with the value of the first separator on the root page, Baf.
As the value Athens is less than Baf, the database system continues the search on the first index page of the B* tree index level.
2. The first separator – An – on the first index page of the B* tree index level is less than the value Athens. So the database system evaluates the next separator - Au – on the index page.
Because the value Au is greater than the value Athens, the database system evaluates the address information following the separator An in order to get to the correct leaf page on the leaf level.
3. To find the address information in the data record with the key value Athens, the database system uses a binary search algorithm.
The database system searches the data records on the leaf page until it finds the data record it is searching for. That completes the search.