こんにちは、 @kz_morita です。

SQL Server のインデックスについてまとめてみます。

(Qiita から移動された記事の内容になります)

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 のインデックスについて簡単に紹介させていただきました。 インデックスをただしく利用し、効率よくデータを取得することはとても重要です。特に大量のアクセスが同時に集まるようなシステムの場合、致命的な問題になりかねません。 設計段階で、インデックスについて十分に留意しておくことが重要だと思います。