SQL Performance Explained

PostgreSQLインデックスの仕組み

インデックスとは？

• インデックスは クエリを高速化するためのデータ構造
• CREATE INDEXで作成され、テーブルのデータをコピーした冗長構造を持つ
• 本の「索引」と同じように、実データへの参照であり、独立したディスク領域を消費する

クラスタ化インデックス

• SQL Server / MySQL (InnoDB) → クラスタ化インデックスを採用
• Oracleでは IOT (Index-Organized Table) と呼ばれる
• テーブル自体がインデックス構造で格納される仕組み
• メリット・デメリットは後章で解説

電話帳の比喩

• インデックスは「整列された電話帳」のようなもの
• 整列済みだから検索は速い
• ただし電話帳は更新ができず、次の改訂で反映するしかない
• SQLデータベースは INSERT / UPDATE / DELETE を即時に反映しなければならない → より複雑な仕組みが必要

インデックスを支える2つのデータ構造

1. 二重リンクリスト (Doubly Linked List)

   • 論理的な順序を維持
   • ノードが前後のノードを参照することで「チェーン状」に接続
   • 新規データ挿入時、物理位置に関わらずリンクの更新だけで済む
   • 大量データ移動なしで高速な挿入・削除が可能

2. 探索木 (Search Tree, B-Tree)

   • データを効率的に検索するための構造
   • リストだけでは逐次探索になるが、木構造により特定キーへ高速アクセス可能

まとめ

• インデックスは冗長データだが、クエリ性能に必須
• その性能特性は 探索木 + 二重リンクリスト によって支えられている
• 今後の章で、WHERE句・JOIN・ORDER BYなどのパフォーマンスとの関係が解説される予定

---