インデックスの仕組み：データ構造と検索アルゴリズム

今日はインデックスのアーキテクチャをもっと深く掘り下げて、実際にどう動いてるのか見ていこう。インデックスの仕組みを知ってると、なんでクエリが速くなるのかだけじゃなくて、いろんなケースで最適なインデックスを選ぶコツもわかるようになるよ。

インデックスの構造って言うと、データがインデックスの中でどう整理されてるかって話。書類がごちゃっと積まれてる棚を想像してみて。全部バラバラだと探すの大変だけど、アルファベット順に並んでたらすぐ見つかるよね。インデックスもそんな感じで、データをうまく並べて、必要な情報をめっちゃ速く探せるようにしてるんだ。

B-TREEインデックスの構造

B-TREE（balanced tree — バランスの取れた木構造）は、PostgreSQLで一番よく使われてるインデックスタイプ。ざっくり言うと、ツリー構造になってて、データがノードに整理されてて、検索はツリーの根っこから葉っぱまでたどっていく感じ。

イメージはこんな感じ：

         ルート
          /       |       \
      ノード1    ノード2    ノード3
     /   \       |       /   \
リーフ1 リーフ2   リーフ3  リーフ4 リーフ5

それぞれのノードには検索のためのキー値が入ってて、検索を誘導してくれる。例えば、ルートノードに[10, 20, 30]があったら：

• 10より小さいデータはリーフ1にある。
• 10と20の間のデータはリーフ2、みたいな感じ。

B-TREEインデックスのメリット：

• データ検索が速い：検索の複雑さはO(log n)で、線形検索より全然速い。
• 範囲検索にも向いてる（例えば10から50までの値を探すとか）。

例： 例えば、studentsテーブルにageカラムがあるとする。このカラムにB-TREEインデックスを作ると：

CREATE INDEX age_idx ON students (age);

PostgreSQLは年齢の値でバランスの取れた木を作ってくれるから、特定の年齢や年齢の範囲の学生をすぐ見つけられる。

B-TREEでの検索アルゴリズム

クエリを実行するとき、PostgreSQLはインデックスを使ってこんな感じでデータを探す：

1. 検索キーを決める（例えば年齢25）。
2. ルートノードからスタート。
3. キーをノードの値の範囲と比べて、該当する子ノードに進む。
4. リーフにたどり着くまで3を繰り返す。
5. リーフからキーに合うデータを返す。

クエリ例：

SELECT * FROM students WHERE age = 25;

インデックスがあると、スキャンするデータ量が減って、検索がめっちゃ速くなる。

検索アルゴリズムとパフォーマンス

インデックスは、スキャンしなきゃいけない行数を減らすことで検索を速くしてる。インデックスがないと、PostgreSQLはテーブル全体をスキャンする（これをシーケンシャルスキャンまたはSeq Scanって呼ぶ）。インデックスがあるとインデックススキャン（Index Scan）になるから、こっちの方が断然速い。

シーケンシャルスキャンとインデックススキャンの比較

• シーケンシャルスキャン（Seq Scan）：

  • PostgreSQLはテーブルの全行を読んで、クエリ条件をチェックして、合う行を返す。
  • インデックスがない場合や、クエリがほぼ全行を対象にしてる場合に使われる。

• インデックススキャン（Index Scan）：

  • PostgreSQLはインデックスを使って該当する行を探してから、その行だけテーブルにアクセスする。
  • 大きなテーブルで、少ないデータだけ取り出すクエリならめっちゃ速い。

例： インデックスなしで年齢検索

SELECT * FROM students WHERE age = 25;

この場合、100万行全部読むことになるかも。でもB-TREEインデックスがあれば、例えば100行だけ読めばOK。

インデックス構造がパフォーマンスに与える影響

インデックスが速いのは、スキャンするデータ量を減らしてくれるから。例えば、テーブルに何百万行あっても、インデックスがあれば数個のノードだけ読めば済む。

インデックスの構造をちゃんと理解するのは超大事。どう動いてるか知ってると、なんでクエリが遅いのか、どうやったら速くなるのかもわかるようになる。

それに、どのインデックスを使うべきかも大事。範囲検索ならB-TREEがいいし、配列やJSONBならGIN。インデックスの選び方を間違えると、逆にDBが遅くなることもあるよ。

実際の例

じゃあ、インデックスがどう役立つか見てみよう。

ソート用インデックス

CREATE INDEX salary_idx ON employees (salary);
SELECT * FROM employees ORDER BY salary;

B-TREEインデックスがあれば、PostgreSQLはインデックスから直接ソート済みデータを返せるから、追加のソート処理がいらない。

範囲検索用インデックス

CREATE INDEX price_idx ON products (price);
SELECT * FROM products WHERE price BETWEEN 100 AND 500;

B-TREEインデックスなら、指定した範囲に入る行をすぐ見つけられる。

よくある質問と落とし穴

なんでインデックスをいつも使えばいいってわけじゃないの？ インデックスはディスクの容量を食うし、INSERT・UPDATE・DELETEのたびにインデックス構造も更新しなきゃいけないから、書き込みが遅くなる。だから、よく使うカラムだけにインデックスを作るのが大事。

インデックスが効かない場合は？ テーブルのほとんど全部を対象にするクエリ（例えばWHERE true）だと、PostgreSQLはSeq Scanを選ぶ。インデックスノードを読むメリットがないからね。