こんにちは、 @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 をもとに、実データへアクセスしデータを取得する仕組みが非クラスタ化インデックスです。 この実データへのアクセスをページジャンプといいます。