ADDRESS テーブルで、CITY 列が一次キーとして定義されています。ユーザは以下の SELECT 文を入力しています。
SELECT * FROM address WHERE city=′Athens′
データベースシステムによって、CITY 列に値 Athens があるデータレコードが ADDRESS テーブルで検索されます。
...
1. 検索は B* ツリーのルートレベルで開始されます。値 Athens が、ルートページの最初の区切記号の値である Baf と比較されます。
値 Athens は Baf よりも小さいため、B* ツリー索引レベルの最初の索引ページで検索が続行されます。
2. B* ツリー索引レベルの最初の索引ページにある最初の区切記号 An は、値 Athens よりも小さい値です。したがって、データベースシステムでは、索引ページにある次の区切記号 Au を評価します。
値 Auは Athensよりも大きいため、データベースシステムでは、リーフレベルの正しいリーフページにアクセスするために、区切記号 Anに続くアドレス情報が評価されます。
3. キー値 Athens を持つデータレコードのアドレス情報を検索するために、データベースシステムではバイナリ検索アルゴリズムが使用されます。
検索対象のデータが見つかるまで、リーフページのデータレコードが検索されます。これで検索は完了します。
参照: