はじめに
こんにちは。今回は、インデックスについてまとめます。
インデックスとは、データベースに高速にアクセスするためにデータとは別の領域に用意された索引です。インデックスの種類には、B木やビットマップなどがあります。
本文
インデックス
インデックス（索引）とは、データベースのレコードを取得するときに利用するものです。インデックスは基本的に、検索に使用する列の値と、その値に対応するレコードにアクセスするためのポインタの２つの組みで構成されています。
ハードディスクなどのメディアに、テーブルとは別にインデックスのための記憶領域を用意しておきます。検索時には、最初にインデックスを検索してから、対応するポインタを用いてテーブルにアクセスします。
ポインタは、データなどにアクセスするときに、参照するテーブルの位置を示すための情報です。C/C++言語のポインタは基本的にメモリアドレスですが、DBMSのインデックスでのポインタにはデータが格納される記憶装置（ハードディスクなど）のアドレスを使用します。
インデックスを使用することで、データの検索時には高速にテーブルにアクセスすることが可能になります。しかし、データの更新時にはインデックスの再構築が必要になるので、かえって時間がかかることが多くなってしまいます。更新頻度や使用状況に合わせて、適切にインデックスを設計することが大切です。
インデックスのデータ構造
インデックスのデータ構造には大きく分けて、B木、ビットマップ、ハッシュの3種類があります。
1. B木（B tree）
B木インデックスは、最も一般的なインデックスです。
木構造の１つで、データをツリー状に管理します。１つの根から２つ以上の分岐を行う多分木で、根から葉までの高さ全てのデータで同じバランス木です。2分探索木と同じように、データの大きさを比較することで、該当するデータを探索していきます。
例えば、次のようにデータを繋げることで探索を高速化します。
B木では、１つ１つのデータの塊をノードと言います。
一番上のノードを根ノード、一番下のノードを葉ノードと呼びます。根以外のノードに含まれるデータの数は、最大のデータ数をnとすると、n/2以上n以下となります。
また、B木の応用例として、データをすべて葉に持たせ葉ノードを順に探索していくことで順次探索を高速に行うB+木があります。B木をB+木にすると次の図のようなイメージになります。
さらに、ノードに含まれるデータの再定数を最大値の2/3以上にして効率化を図ったB*木もあります。
B木やB木を応用した木は、特定の１つのデータを探すのに向いているので、主キーなどによく設定されます。
また、値の大小が比較しやすいので、範囲検索も可能です。
ただし、木を探索してデータにアクセスするため、検索条件は１つしか指定できず、ANDやORの条件指定などで複数のインデックスを同時に使うことはできません。
2. ビットマップ
ビットマップインデックスは、取り得る値の数が少なく、複雑な探索が行われる場合に利用されるインデックスです。データウェアハウスなどでよく利用されます。
例えば、ユーザを管理するデータベースがあり、その中の項目の"性別"は、「男性」「女性」「それ以外」の3種類のいずれかの値のみ取ることとします。このとき、「男性」「女性」「それ以外」のそれぞれについて次のようなビットマップを用意します。
データの探索時には、これらのビットマップを検索し、１に当てはまるデータをポインタでたどります。このインデックスによって、種類の少ない数多くのデータにアクセスすることが容易になります。
また、ビットマップは、ANDやORの条件指定など、複雑に処理を組み合わせることが可能です。例えば、上記のビットマップでは、次のような複数の条件を組み合わせた場合でも高速にインデックスを使用できます。
-- 例
SELECT * FROM ユーザ
WHERE 性別 = '女性' OR 性別 = 'それ以外'
3. ハッシュ
ハッシュインデックスは、ハッシュ関数と呼ばれる関数を使って、検索に使用するキーからハッシュ値を計算し、その値からデータの格納位置を求めます。
例えば、ハッシュ関数として、"キー値%5"（5で割った余り）を用意し、その結果で求められた値の番地にデータを格納します。
図にすると次のようになります。
ハッシュ関数を利用するため、データが増えても検索を高速に行うことができます。しかし、ハッシュの格納場所のサイズはあらかじめ決まっており、ハッシュ値の衝突が発生するような大量のデータなどの利用には向いていません。
ユニーク/非ユニークインデックス
インデックスには、インデックス値に対応するレコードが１つしかないユニークインデックスと、複数のレコードが１つのインデックス値に対応する非ユニークインデックスがあります。
主キーや値が重複しない列のインデックスはユニークインデックスですが、それ以外の外部キーなどに設定するインデックスは非ユニークインデックスです。
非ユニークインデックスの場合は、あるキー値に対応するデータが複数あるため、そのデータの格納位置情報（ポインタ）を複数持ちます。
クラスタ化/非クラスタ化インデックス
インデックスは、基本的にデータの格納位置情報（ポインタ）を管理するだけです。そのため、記憶装置にバラバラに格納されることが多くなります。しかし、実際にデータを読み込むときにはバラバラに格納されていると非効率なため、キー値ごとにデータの格納位置を定め、同じ場所に格納することがあります。この作業をクラスタ化といい、クラスタ化したデータのインデックスのことをクラスタ化インデックスと言います。
データの実際の格納位置を操作するため、クラスタ化できるインデックスは１テーブルにつき1種類に限られます。クラスタ化インデックス以外は、非クラスタ化インデックスとなります。
性能設計
インデックスは、設定することで高速化を実現できることがありますが、返って処理が遅くなるといった問題を招くものでもあります。そのため、データの性質をしっかり考えて性能設計を行うことが大切です。
インデックス設計
インデックスを設定すると、SELECT文でデータを検索するときのアクセスは速くなりますが、INSERT, UPDATE, DELETE文では、使用するたびにインデックスの再構成の必要があり、処理が遅くなります。
そのため、インデックスは状況に応じて適切に設定しなければなりません。インデックス設計では、データ後続だけでなく、データ量や更新頻度など、様々な要素を考慮して、どの列にインデックスを設定するかを考えていきます。
インデックス設計のポイント
- １つのテーブルにインデックスを設定しすぎない
1つのテーブルに多数のインデックスがあると、テーブルのデータが変更された場合に全てのインデックスの再構成が行われるため、更新時の影響が大きくなります。そのため、よく使われる列を最小限使ってインデックスを設定することが大切です。
- データ量が少ないときには設定しないほうがいい場合もある
データ量が少ないときには、インデックスからアクセスするよりも直接テーブルにアクセスして順番に検索したほうが早い場合も多々あります。予想されるデータ量と速度を比較し、小さなテーブルの場合にはインデックスの設定を行わないという選択肢もあります。
- クラスタ化インデックスは、頻繁に利用される一意性が高い列に設定する
クラスタ化インデックスは、１つのテーブルに１つしか設定できません。順に並べる場合には、主キーなどの一意性が高いキーが適しているので、一般的には主キーに設定するのが最も効果的です。
速度や処理時間の測定・演算
SQLの処理時間は、インデックスが使われるかどうか、データがクラスタ化されているかどうかで大きく変わります。
細かい仕様はDBMSにより異なりますが、一般的なRDBMSの仕様では、速度に影響する処理時間は次のような要件を考慮して求めます。
- 索引検索は、索引を読み込んでからデータを読み込む
データベースの検索には、インデックスを使わない表検索とインデックスを使用する索引検索があります。索引検索では、一度索引のデータページを読み込み、そこのデータをもとに、データが格納されているデータページを読み見込みます。そのため、非効率なインデックスであれば、表検索でデータを１つずつ順番に確認していったほうが高速な場合もあります。
- クラスタ化インデックスは、範囲内の複数のデータにアクセス可能
クラスタ化インデックスでは、キー値の順にデータがまとまって格納されています。そのため、範囲検索（VETWEENや比較演算子など）などで複数のデータを取得する場合には、同じデータページに目的のデータが複数格納されていることがあり、この場合には効率的にデータを取得できます。
- データだけでなくログの出力時間も考慮する
データを更新する場合には、更新前ログや更新後ログなどのログを取得することが一般的です。そのため、処理時間には、データの更新時間に加えて、ログを更新する時間も考慮に入れる必要があります。また、更新時にはインデックスの再構成が起こることがあるので、この時間も考慮します。
ディスク容量の計算
インデックスは、データを格納するディスク領域の他に、インデックスのためのディスク領域を必要とします。B木などでは、木構造に合わせて複数のデータページが必要となります。インデックスを作成するたびにインデックス用の領域が必要になるので、ディスク容量の計算にはインデックスを考慮に入れなければなりません。
テーブルの表領域の容量は、一般的に1行あたりの平均行長（バイト）×見積行数で求められます。データページの１ブロックは通常1024バイト、8192バイトなどのような1024の正数倍の値を指定します。テーブルの1行を複数のブロックに分けて格納することはないので、ブロックごとに格納できる行数は、ブロックサイズ÷平均行長（小数点以下切り捨て）で求められます。
パーティション化
パーティション化（パーティショニング）は、１つのテーブルのデータを分割して管理する方法です。論理的に区分けしたものをパーティションと言い、パーティションキーを設定し、パーティションキーごとにデータを分割していきます。
パーティション化を行うことによって、一部のデータにだけアクセスするためにテーブル全体を読み込む必要があなくなり、性能が向上します。
まとめ
いかがでしたでしょうか？