いまさら聞けないSQL Server 2005のインデックス　その１

インデックスとは

インデックスとは、データベースの索引の役割を果たすものである。

辞書の中から、必要な情報にアクセスしたい場合、辞書のはじめのページから順に探していく人はいない。
そんなことをしてては日が暮れてしまう。辞書を引くときは、索引を有効に活用し、
ページをめくる回数を最小限におさえ、必要な情報を効率的に取得します。
データベースの場合も同様に、あらかじめデータに関する索引を生成しておけば、
データ検索の際のディスク・アクセス回数を減らすことができ、
効率的な検索が期待できる。これがインデックスである。

このとき、インデックスの効果が期待できるのは、SELECT文によるデータの参照時に行われる検索。
あるいは、UPDATE文やDELTE文の場合も、変更対象となるデータを見つけ出す必要があるため
同様に検索処理が行われることとなり、索引であるインデックスが有効となる。

SQL Serverのページとは？

ページとは、SQL ServerにおけるデータI/Oの最小単である。

ページは８Kバイトの連続したディスク領域で、SQL Serverは１Mバイトあたり１２８ページあることになる。
各ページの先頭には９６バイトのヘッダーがあり、ここには各ページに関するシステム情報が格納されている。
この情報には、ページ番号、ページの種類、ページ上の空き容量、
そのページを所有しているオブジェクトのアロケーションユニット IDなどが含まれる。
データ行はヘッダーの直後から始まり、ページ上に連続的に配置される。
ページの末尾からは、行オフセットテーブル情報が格納される。
各行オフセットテーブルには、ページ上の１行につき１つのエントリが格納される。
各エントリには、その行の最初のバイトがページの先頭からどれだけ離れているかの位置情報が記録されている。
このとき、行オフセットテーブル内のエントリは、ページ上のデータ行行と逆順に並んでいる。
また、すぺてのページはエクステントに格納される。
エクステントは、物理的に連続する８ページをまとめたもので、ページを効率的に管理するために使用される。

ページにはデータ行やインデックスに使用されるポインタなどの情報が格納される。
テーブルにインデックスがない場合、検索対象となるデータ行を探すために
テーブル全データ行をメモリに読み込んで、検索条件に合ったデータかどうかを比較する必要がある。
仮に１件のデータ行のサイズが８Kバイトで定義されている場合、そこに10万件のデータを格納すると、
データファイル内に10万ページ分の割り当てが行われることになる。
この10万ページ分のデータに対して検索すると、10万ページ分の物理IOが発生し、
メモリのバッファキャッシュ内で約780Ｍ（8192*100000)バイトもの大きな領域を消費してしまうこととなる。

Ｂツリー構造とは？

辞書の索引では、いわば単純な配列構造であるが、
データベースの索引(インデックス)は、ツリー構造となっていて、
Ｂツリー(BalanceTree)構造と呼ばれる形でページが構成されている。

Ｂツリーの最上位ノードをルートノード、インデックス内の最下位レベルのノードをリーフノードと呼ぶ。
ルートノードとリーフノードの間に位置するインデックスレベルを中間ノード(ブランチノード)と呼ぶ。
また、インデックスとなる中間ノードとリーフノードでは、
それぞれ同じレベルに位置する隣接したページ間のリンクリストを保持している。

データ行を格納しているページをデータページと呼び、
インデックスを格納しているページをインデックスページと呼ぶ。
Bツリーのインデックスページには、検索で使用されるキー列の値と、下位レベルへのポインタが含まれ、
検索対象であるデータページに到達するまでのI/O回数は
データがどのページに格納されていたとしても、必ず等しくなる。また、ポインタのサイズは６バイトである。

１０万件のデータに対するインデックスを考える。検索で使用されるキー列が
４バイトのint型で定義されているとき、インデックス行を管理するためのオーバーヘッドも考慮して、
１インデックス行あたり１５バイト程度。１インデックスページは８Kバイトであるから、
１インデックスページあたり約５３３データ行へのポインタを格納できる計算となる。
つまり、１０万件のデータに対する中間ノード(レベル１)へのインデックスページは
１８７ページあればよく、その上位の中間ノード(レベル２)は、その１８７ページへのポインタを格納すればよい。
つまり、データが１０万件あったとしても、完全一致検索では、
ルートノードのページ→中間ノードのページ→リーフノードのページ(データ行)への検索で、
合計４ページ分(32KByte)のアクセスだけでデータを取得することができることを意味する。

このように、インデックスを作成することで、テーブル全てのページに対するアクセスをする代わりに、
Ｂツリー構造のインデックスページ使うことによって、効率よく該当するデータを格納している
データページへアクセスすることができるようになる。