データベースのインデックスについて、日常業務でよく触れる機会があるでしょう。例えば、特定のSQLクエリが遅い場合に原因を分析し、「特定のフィールドにインデックスを追加しましょう」といった解決策を提案した経験があるかもしれません。しかし、インデックスとは何であり、どのように機能するのでしょうか。本記事ではこのテーマについて詳しく解説します。

一言で言えば、インデックスはデータ検索の効率化のために存在し、本の目次のようなものです。500ページの本の中から特定の知識を素早く見つけたい場合、目次なしではかな時間がかかります。同様に、データベースのテーブルにとって、インデックスはその「目次」に相当します。

MySQLにはどのようなインデックスタイプがありますか？

インデックスは4つの観点から分類できます。

• 「データ構造」による分類：B+treeインデックス、ハッシュインデックス、全文検索インデックス
• 「物理的ストレージ」による分類：クラスター化インデックス（主キーインデックス）、非クラスター化インデックス（セカンダリインデックス）
• 「フィールド特性」による分類：主キーインデックス、一意インデックス、通常インデックス、プレフィックスインデックス
• 「フィールド数」による分類：単一列インデックス、複合インデックス

次に、これらの観点から各インデックスの特徴について説明します。

データ構造による分類

データ構造の観点から、MySQLで一般的なインデックスにはB+Treeインデックス、ハッシュインデックス、全文検索インデックスがあります。

テーブルを作成する際、InnoDBストレージエンジンは異なるシナリオに応じて異なる列をインデックスとして選択します：

B+ツリー

• 主キーがある場合、デフォルトで主キーをクラスター化インデックスのキーとして使用します
• 主キーがない場合、NULL値を含まない最初の一意の列をクラスター化インデックスのキーとして選択します
• 上記の両方がない場合、InnoDBは自動的に隠れの自動増分ID列をクラスター化インデックスのキーとして生成します

その他のインデックスはすべてセカンダリインデックス（Secondary Index）に属し、セカンダリインデックスまたは非クラスター化インデックスとも呼ばれます。作成された主キーインデックスとセカンダリインデックスはデフォルトでB+Treeインデックスを使用します。

B+Treeは多分木の一種で、データはリーフノードにのみ格納され、非リーフノードにはインデックスのみが格納されます。また、各ノード内のデータは主キーの順序で格納されています。各親ノードのインデックス値は子ノードのインデックス値にも現れるため、リーフノードにはすべてのインデックス値情報が含まれています。さらに、各リーフノードには次のリーフノードと前のリーフノードを指す2つのポインタがあり、双方向リンクリストを形成しています。

主キーインデックスのB+Treeは以下の通りです：

1. データの組織形式：InnoDBストレージエンジンの主キーインデックスB+ツリーの非リーフノードにはインデックスキーと子ノードへのポインタのみが格納され、実際のデータは格納されません。これはMySQLのインデックスに対応します。リーフノードにはインデックスキーと行データが格納されるため、InnoDBストレージエンジンの主キーインデックスはクラスター化インデックスに属します
2. リーフノードのリンクリスト：すべてのリーフノードはポインタで接続され、双方向リンクリストを形成し、高速な順次アクセスと範囲クエリをサポートします
3. バランスツリー構造：すべてのリーフノードは同じレベルにあり、ツリーの高さはバランスが取れています。これにより、任意のデータレコードの検索、挿入、削除操作のパス長が同じになり、安定性が高まります

他のインデックスの詳細は以下の記事をご参照ください：

なぜMySQLはB+ツリーをインデックスとして使用するのか？

物理的ストレージによる分類

物理的ストレージの観点から、インデックスはクラスター化インデックス（主キーインデックス）と非クラスター化インデックス（セカンダリインデックス）に分けられます。

クラスター化インデックスと非クラスター化インデックスの違いは何ですか？

これらの主な違いはB+ツリーのリーフノードに格納される内容が異なる点にあります：

クラスター化インデックス

• クラスター化インデックスのB+ツリーのリーフノードには主キー値+完全なレコードが格納されます

非クラスター化インデックス

• 非クラスター化インデックスのB+ツリーのリーフノードにはインデックス値+主キー値が格納されます

したがって、クエリでセカンダリインデックスを使用する場合：

クエリのデータがセカンダリインデックスにない場合、まずセカンダリインデックスを検索し、対応するリーフノードを見つけて主キー値を取得し、次に主キーインデックスを検索してデータを取得します。このプロセスをバックアップ（回表）と呼びます。

クエリのデータがセカンダリインデックスで検索できる場合、バックアップは不要で、このプロセスをカバリングインデックスと呼びます。

フィールド特性による分類

フィールド特性の観点から、インデックスは主キーインデックス、一意インデックス、通常インデックス、プレフィックスインデックスに分けられます。

主キーインデックス

主キーインデックスは主キーフィールドに作成されるインデックスで、通常はテーブル作成時に一緒に作成されます。1つのテーブルに主キーインデックスは1つしか存在できず、インデックス列の値にNULL値は許容されません。

テーブル作成時に主キーインデックスを作成する方法は以下の通りです：

CREATE TABLE customer_table  (
  id INT AUTO_INCREMENT,
  name VARCHAR(100),
  email VARCHAR(100),
  PRIMARY KEY (id) USING BTREE
);

一意インデックス

一意インデックスはUNIQUEフィールドに作成されるインデックスで、1つのテーブルに複数の一意インデックスを持つことができます。インデックス列の値は一意である必要がありますが、NULL値は許容されます。

テーブル作成時に一意インデックスを作成する方法は以下の通りです：

CREATE TABLE product_table  (
  id INT AUTO_INCREMENT,
  product_code VARCHAR(50),
  product_name VARCHAR(100),
  UNIQUE KEY(product_code) 
);

テーブル作成後、一意インデックスを作成するには以下のコマンドを使用します：

CREATE UNIQUE INDEX idx_email
ON user_table(email); 

通常インデックス

通常インデックスは通常のフィールドに作成されるインデックスで、フィールドが主キーである必要も、UNIQUEである必要もありません。

テーブル作成時に通常インデックスを作成する方法は以下の通りです：

CREATE TABLE order_table  (
  order_id INT AUTO_INCREMENT,
  customer_id INT,
  order_date DATETIME,
  INDEX(customer_id) 
);

テーブル作成後、通常インデックスを作成するには以下のコマンドを使用します：

CREATE INDEX idx_order_date
ON order_table(order_date); 

プレフィックスインデックス

プレフィックスインデックスは文字型フィールドの先頭の数文字に作成されるインデックスであり、フィールド全体に作成されるインデックスではありません。プレフィックスインデックスはchar、varchar、binary、varbinary型の列に作成できます。

プレフィックスインデックスを使用する目的は、インデックスが占有するストレージ領域を削減し、クエリの効率を向上させることにあります。

テーブル作成時にプレフィックスインデックスを作成する方法は以下の通りです：

CREATE TABLE article_table(
    id INT AUTO_INCREMENT,
    title VARCHAR(255),
    content TEXT,
    INDEX(title(20))
); 

テーブル作成後、プレフィックスインデックスを作成するには以下のコマンドを使用します：

CREATE INDEX idx_title_prefix
ON article_table(title(20)); 

フィールド数による分類

フィールド数の観点から、インデックスは単一列インデックス、複合インデックスに分けられます。

• 単一列に作成されるインデックスを単一列インデックスと呼びます（例：主キーインデックス）
• 複数列に作成されるインデックスを複合インデックスと呼びます

複合インデックス

複数のフィールドを組み合わせて1つのインデックスにしたものを複合インデックスと呼びます。

例えば、商品テーブルの商品番号(product_code)と名前(product_name)フィールドを複合インデックス(product_code, product_name)として組み合わせる場合、複合インデックスの作成方法は以下の通りです：

CREATE INDEX idx_product_code_name ON product(product_code, product_name);

複合インデックス(product_code, product_name)のB+Treeの図示は以下の通りです

図からわかるように、複合インデックスの非リーフノードでは2つのフィールドの値をB+Treeのキー値として使用します。複合インデックスでデータをクエリする場合、まずproduct_codeフィールドで比較し、product_codeが同じ場合にproduct_nameフィールドで比較します。

つまり、複合インデックスのB+Treeはまずproduct_codeでソートされ、product_codeが同じ場合にproduct_nameフィールドでソートされます。

したがって、複合インデックスを使用する際には最左一致の原則が存在し、最左優先の方式でインデックスのマッチングが行われます。複合インデックスを使用してクエリする際に、「最左一致の原則」に従わないと、複合インデックスは無効になり、インデックスを利用した高速なクエリ特性を活用できなくなります。

最左一致の原則

例えば、(a, b, c)の複合インデックスを作成した場合、以下のクエリ条件では複合インデックスと一致します：

• where a=1；
• where a=1 and b=2 and c=3；
• where a=1 and b=2；

注意すべき点は、クエリオプティマイザがあるため、where句でのaフィールドの順序は重要ではないということです。

したがって、以下のようなクエリ文を作成した場合：

• where b = 1 and c = 3 and a = 1;

依然として(a、b、c)の複合インデックスを使用できます。

しかし、以下のクエリ条件では、最左一致の原則に合致しないため、複合インデックスと一致せず、複合インデックスは無効になります：

• where b=2；
• where c=3；
• where b=2 and c=3；

これらのクエリ条件が無効になる理由は、(a, b, c)複合インデックスはまずaでソートされ、aが同じ場合にbでソートされ、bが同じ場合にcでソートされるためです。したがって、bとcはグローバルに無秩序ですが、ローカルには相対的に秩序があります。このため、最左一致の原則に従わない場合、インデックスを活用できません。

複合インデックスの範囲クエリ

複合インデックスにはいくつかの特殊なケースがあり、クエリプロセスで複合インデックスを使用しても、複合インデックスのすべてのフィールドが複合インデックスを使用してクエリされているとは限りません。つまり、一部のフィールドは複合インデックスのB+Treeを使用し、一部のフィールドは複合インデックスのB+Treeを使用していない可能性があります。

この特殊なケースは範囲クエリで発生します。複合インデックスの最左一致の原則は、「範囲クエリ」に遭遇すると一致を停止します。つまり、範囲クエリのフィールドは複合インデックスを使用できますが、範囲クエリフィールドの後ろのフィールドは複合インデックスを使用できません。

範囲クエリには多くの種類がありますが、どのような範囲クエリが複合インデックスの最左一致の原則の一致を停止させるのでしょうか。

複合インデックスの最左一致の原則は、範囲クエリ（>、=、 1 and b = 2という文を実行する場合、aフィールドのみがインデックスを使用できます。複合インデックスのB+Treeで最初に条件を満たす主キー値（IDが2）を見つけた後、他の条件が満たされているかどうかを判断する必要があります（bが2に等しいかどうか）。これは複合インデックス内で判断するのでしょうか。それとも主キーインデックスに戻って判断するのでしょうか。

MySQL 5.6以前では、ID2（主キー値）から始めて1つずつテーブルに戻り、「主キーインデックス」でデータ行を見つけ、bフィールド値を比較する必要がありました。

一方、MySQL 5.6で導入されたインデックスプッシュダウン最適化（index condition pushdown）は、複合インデックスの走査過程で、複合インデックスに含まれるフィールドについて先に判断し、条件を満たさないレコードを直接フィルタリングして、バックアップの回数を減らします。

クエリ文の実行計画にExtraとしてUsing index conditionが表示される場合、インデックスプッシュダウンの最適化が使用されていることを示します。

インデックスの識別度

また、複合インデックスを作成する際のフィールド順序は、インデックスの効率にも大きな影響を与えます。前方にあるフィールドほどインデックスフィルタリングに使用される可能性が高く、実際の開発作業では識別度の高いフィールドを前方に配置する必要があります。これにより、識別度の高いフィールドがより多くのSQLで使用される可能性が高まります。

識別度とは、特定のフィールドの異なる値の個数を「テーブルの総行数で割ったもの」を指し、計算式は以下の通りです：

識別度計算式：

例えば、性別の識別度は非常に小さく、インデックスを作成するのに適していませんまたは複合インデックス列の前方位置に配置するのに適していません。一方、UUIDのようなフィールドはインデックスとして適しており、複合インデックス列の前方位置に配置するのに適しています。

なぜなら、インデックスの識別度が非常に小さい場合、フィールドの値が均一に分布していると、どの値を検索しても半分のデータが得られる可能性があるからです。これらの場合、インデックスがない方が良いかもしれません。なぜなら、MySQLにはクエリオプティマイザも存在し、クエリオプティマイザが特定の値がテーブルのデータ行に現れる割合（一般的なしきい値は"30%"）が高いと判断すると、通常はインデックスを無視してフルテーブルスキャンを行うからです。

参考記事：

小林coding——インデックスに関する一般的な面接問題