SQLServerについて
SQLServerのインデックスについて学ばせていただく機会があり、ものすごく勉強になったのでまとめます。
はじめに
他のDBと同様にSQLServerにもインデックスの概念は存在します。
インデックスとは、DBデータの検索を高速に行うための索引のようなものです。
これがあることによって、データベース内すべてを検索せずに目的のデータを特定することができる便利なしくみです。
SQL Serverにおいてインデックスの種類は以下のようになっています。
- ヒープ表（インデックスなしのテーブル）
- クラスタ化インデックス
- 非クラスタ化インデックス
- 複合インデックス
- 付加列インデックス
インデックスは大きく分けてクラスタ化、非クラスタ化にわかれ、非クラスタ化インデックスの中に複合インデックスや、付加列インデックスといったものがあります。
これらを順に説明していきます。
ヒープ表
SQLServerでは、インデックスの作成されていない通常のテーブルをヒープ表と呼びます。
ヒープ表では、挿入されたデータはハードディスクの様々な位置に格納されます。
検索の際には、目的のデータがどこにあるかを先頭から順に走査していきます
そのため検索に必要なオーダーはO(n)になります。
データ量が多くなればなるほど検索時間は比例して増えてしまうため、通常はテーブルにインデックスをはることになります。
クラスタ化インデックス
SQLServerはインデックスの仕組みとしてB-Treeを採用しています。
そのため、インデックスをはるとO(logn)以下でデータの検索を行うことができます。
B-Treeについてはこちらのサイトが非常に参考になります。
クラスタ化インデックスにおいてデータはインデックスに指定したキーの値によってソートされてディスクに格納されます。
結果的にB-Treeのリーフ（一番下の先端にあたる場所）にデータが格納されるイメージです。
クラスタ化インデックスに指定したキーで検索する場合、ルートからノードをたどっていけば目的のデータにたどりつけます。
よってO(logn)で目的のデータを探すことができます。
一般的に、クラスタ化インデックスはPrimary Keyの値で作成されます。
非クラスタ化インデックス
クラスタ化インデックスはデータをソートして格納するので、一つのテーブルに対してひとつまでしか作成できません。
それに対して、複数個作成できるのが非クラスタ化インデックスです。
非クラスタ化インデックスのリーフノードには、実データへの参照が格納されています。
この参照をレコードIDといい、以降RIDと表記します。
このRIDをもとに、実データへアクセスしデータを取得する仕組みが非クラスタ化インデックスです。
この実データへのアクセスをページジャンプといいます。
複合インデックス
通常のインデックスの場合、各ノードには一つのインデックスキーのみが格納されています。
複数カラムをインデックスのキーに指定すると、複合インデックスとなります。
例えば、user_idとitem_idという二つのカラムをインデックスキーとして設定するような場合です。
ここで注意しなければいけないのが、user_id, item_idがユニークでなく同じデータが大量にあった場合、大量のRIDを保持しなければいけないため、インデックスサイズが大きくなってしまいます。
また、複合インデックスでも非クラスタインデックスと同様にリーフノードからページジャンプが起こり実データにアクセスします。
しかし、利用したいデータがuser_idとitem_idのみであった場合、欲しいデータはインデックスツリーが保持しているため実データ領域へとアクセスする必要がなくなります。
このことを生かして、取得するデータをすべてインデックスに含めてしまおうという考えがあります。
この方法がカバーリングインデックスと呼ばれます。（インデックスがクエリをカバーするともいう）
うまく使うと、ディスクI/Oを減らせるため有効な手法となります。
付加列インデックス
複合インデックスでは、インデックスツリーの各ノードに複数のキーを持たせられることを説明しました。
しかし、複数キー持たせるということはそれだけインデックスのサイズが大きくなってしまうということでもあります。
そこで、付加列インデックスという手法がよく用いられます。
すべてのノードに複数カラムのデータを保持するのではなく、リーフノードにのみカラムを追加する（列を付加する）ことで、ページジャンプを防ぐとともに、インデックスのサイズも押さえることができます。
まとめ
SQL Serverのインデックスについて簡単に紹介させていただきました。
インデックスをただしく利用し、効率よくデータを取得することはとても重要です。特に大量のアクセスが同時に集まるようなシステムの場合、致命的な問題になりかねません。
設計段階で、インデックスについて十分に留意しておくことが重要だと思います。