概要

DBを扱う実装を進める上で、切っても切れない関係なのがインデックスです。
私が実務でインデックスを扱う場面に初めて遭遇した時、当初の理解度は
「インデックスを貼ると速くなるんだ〜」
といったレベルで、なぜ速くなるのかまで理解できておりませんでした。
本記事では、インデックスが何者なのか・なぜ速くなるのか・どう使えばいいのかを整理します。

そもそもインデックスとは

インデックスは、データ検索を高速で行うために使用されます。
辞書における「索引」をイメージすると分かりやすいです。

例えば、ランダムな順番で書かれた果物リストから「リンゴ」を検索すると仮定します。
リンゴは一番右にあるので、左から順に検索すると最大8回の検索が必要となります。
ちなみに、端から端まで順に検索することをフルスキャンと言います。

インデックスとして「行別の分類」を使い、並び順を整理してみます。
この分類を使うと、2回の検索でリンゴまでたどり着けます。

インデックスを使うことで、検索対象を事前に整理でき、探す手間を減らすことができます。

インデックス(B-Treeインデックス)の仕組み

インデックスの種類はいくつかありますが、今回はその代表格「B-Treeインデックス」を紹介します。

B-Treeインデックスは「木構造」でデータを管理する仕組みです。
まず木構造とは何かを押さえてから、B-Tree固有の話に進みましょう。

木構造とは

木構造とは、データを親子関係で階層的に管理するデータ構造です。
以下の用語を押さえておけば、後の説明がスムーズに読めます。

ノード：ツリー内の1つの箱
ルートノード：一番上のノード
リーフノード：末端のノード（子を持たないノード）
キー：ノードの中に格納されている値

なぜB-Treeインデックスが必要なのか

木構造は便利ですが、データの入れ方によって形が崩れるという問題があります。
例えば果物を五十音順に1つずつ追加していくと、以下のような木構造となる場合があります。

これでは、インデックスなしのフルスキャンと大差がありません。

そこで「B-Treeインデックス」の出番です。
B-Treeインデックスは自動的にバランスを保つ仕組みを持っています。
特定のデータだけ検索回数が増える、という状況が起きません。

B-Treeインデックスの特徴

改めて、B-Treeインデックスの特徴を整理していきましょう。
前セクションに記載の通り、B-Treeは自動的にバランスを保つ仕組みを持っています。
それを実現しているのが、以下の3つの性質です。

① データが常にソートされた状態で保持される
データの挿入・削除のたびに、B-Tree全体の並び順が自動的に整理されます。
「左右どちらに進めば目的のデータに近づくか」を常に判断できます。

② 全てのリーフノードの深さが同じ
どのデータを探しても、ルートからリーフまでのステップ数が同じです。
「運が悪いと遠い」という状況が起きません。

③ 1つのノードに複数のキーを持てる
1回の読み込みで複数のキーと比較できるため、一気に探索範囲を絞り込めます。

この3つが組み合わさることで、データ量が増えても検索・挿入・削除を少ない回数で行えます。
フルスキャンの場合は計算量がO(N)となりますが、B-Treeインデックスを使うとO(logN)で処理できます。

O(N), O(logN) について
O(~)とは、アルゴリズムの計算量を表す記法です。
例えばデータ量が100万（N=1,000,000）の場合、O(N)では100万回計算する必要がありますが、O(logN)の場合、約20回の計算で済みます。

このようにB-Treeインデックスを使うことで、特定のデータへの探索回数を大幅に削減できます。

インデックスの効果的な使い方とその注意点

インデックスの仕組みが分かったところで、実際にどの場面で使うべきか整理します。

特定の句で使用されている

WHERE, ORDER BY, JOINなどで使われているカラムは、インデックスを貼る有力候補となります。

注意点

対象カラムで演算が行われている場合、インデックスの効果は無くなるため注意です。
例えば果物の製造番号のカラム serial_number があるとします。

SELECT * FROM fruits WHERE serial_number * 2 > 10000;

上記にてWHERE句で確認しているのは「serial_numberカラム」そのものではなく「serial_numberの2倍カラム」です。
これは別物のカラムと見なされるため、インデックスが適用されません。

同じような処理でインデックスを適用させたい場合、以下のように書き換えて使用する必要があります。

SELECT * FROM fruits WHERE serial_number > 10000 / 2;

左辺のカラム側で直接演算を行うと、インデックスが適用されない点に留意すべきです。

カーディナリティが高い

カーディナリティとは「データの種類の数」を指しています。

先ほどの果物の例で考えてみましょう。
果物の詳細情報として、「色」と「味」カラムを以下のように定義します。
色は「赤、緑、黄緑、黄、橙、紫」と様々な種類がありますが、味は「甘い、甘酸っぱい」の2種類しかありません。

この場合、カーディナリティが高いのは「色」となります。
リンゴを探す場合、「味」ではなく「色」で検索することで、より少ない件数に絞り込むことができます。

リンゴを「味」で検索する場合：

リンゴを「色」で検索する場合：

カーディナリティが高いカラムにインデックスを貼ると、より効果的に検索できます。

とはいえ、一部のデータに偏っている場合に注意する必要があります。
いくらカーディナリティが高くても、「特定のデータに99%、残り1%が散らばっている」という場合は、検索対象を絞りづらいですよね。

データが100万件あるとして、99万件は同じで、残りの1万件は全部違う値だった場合、フルスキャンとほとんど変わりません。
このような場合、インデックスを貼る意味がほぼ無くなってしまうので注意です。

テーブルが大規模である

先ほどのO(logN)の話にも通じます。
データ数が100万件, 10件の場合、フルスキャンとインデックスを使用した場合は以下の通りです。

データ数が100万件（N=1,000,000）の場合：

フルスキャン: 100万回(O(N)=1,000,000)
インデックス適用: 20回(O(logN)≒20)

データ数が10件（N=10）の場合：

フルスキャン: 10回(O(N)=10)
インデックス適用: 3回(O(logN)≒3)

前者に比べると、後者の効果は微々たるものですよね。

「じゃあどのくらいのレコード数の時使えばいいんだよ」という点ですが、データベースの環境や対象データの使用頻度等によって変わるため、一概には言えません。

ただ10万件を超え始めると、インデックスの恩恵が顕著になると言われております。

前述の「特定の句で使用されているか」「カーディナリティが高いか」という点と照らし合わせて判断する必要があります。

引用元