概要
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万件を超え始めると、インデックスの恩恵が顕著になると言われております。
前述の「特定の句で使用されているか」「カーディナリティが高いか」という点と照らし合わせて判断する必要があります。