索引付テーブルのB* ツリー 
用途
データベースシステムは、基本テーブルに定義されているすべての索引に対して B* ツリーを登録します。
基本テーブルの索引は、SQL 文で明示的に定義され、B* ツリー索引レベルとは無関係です。
データベースシステムでは、索引の倒置一覧が以下のように保存されます。
● 二次キー (索引エントリ) と一次キーとの間の 1 対 1 関係:
倒置一覧は、索引の B* ツリーの対応するリーフページに直接保存されます。
● 二次キーと複数の一次キーとの間の 1 対 n 関係:
倒置一覧は、索引の B* ツリーの対応するリーフページ(フラットリスト) に直接保存されます。
リーフページに対して倒置一覧が大きくなりすぎた場合は、倒置一覧用に別の B* ツリーが登録されます。これにより、索引の B* ツリーのリーフページには、倒置一覧の B* ツリーへの参照のみが含まれるようになります。
例
CUSTOMER テーブルには、ホテルのすべての得意先の名称が含まれています。
● 一次キー:得意先コード cno
● 索引: 姓 name
CUSTOMER テーブル
cno |
surname |
firstname |
2003 |
Miller |
Frank |
2011 |
Griffith |
Mary |
2078 |
Miller |
Jane |
2104 |
Miller |
Susan |
2295 |
Miller |
Sally |
索引には、以下の倒置一覧が含まれています。
倒置一覧
名称 |
二次キー |
一次キー |
倒置一覧 1 |
Griffith |
2011 |
倒置一覧 2 |
Miller |
2003, 2078, 2104, 2295 |
倒置一覧 1 は、索引の B* ツリーのリーフページに直接保存されます。
倒置一覧 2 には追加の B* ツリーが登録されます。索引の B* ツリーのリーフページに十分なスペースがないためです。
参照: