エンジニアの小張です。多くのデータを扱うアプリケーションにとって、ユーザーが求めるデータを返すまでの速さは生命線とも言えます。 試行錯誤を重ねデータの蓄積量が増えれば増えるほど、アプリケーションが使いづらくなってしまったら、悲しいですよね。。。 今回はそんなレスポンス速度向上に必須の知識であるインデックスについて、構造からおさらいしていきたいと思います。

InnoDBのインデックス

インデックスとは、 データベース上でのSELECT、WHEREなどの操作による データの集計・検索の高速化に貢献する技術の1つです。 ここでは、MySQLで使用されるInnoDBのインデックスについて説明します。

B+木(B+Tree)について

MySQLのInnoDBエンジンで使われるインデックスは、B+木というデータ構造で実装されています。 InnoDBのインデックスは、以下の種類があります。
  • クラスタインデックス
  • セカンダリインデックス
  • カバリングインデックス
  • 複合インデックス
これらの詳細は次章で説明します。 まずは、すべてのインデックスの基礎となる、B+木の構造や特徴、挙動などを以下に説明します。

B+木の派生元

B+木は、B木というデータ構造をもとに改良したデータ構造となっています。 B+木の説明に入る前に、その派生元であるB木について説明します。
B木と木構造
B木は、「B木」という名前から見て「木」という文字が使われていることから分かるように、 木構造というデータ構造がベースとなってできています。 実世界にある木(Tree)の構造に見たてています。 木を形成する各部構造は、節と枝はもちろん、根や葉もあります。 上記をそれぞれ英名表記して、ノード、ブランチ、ルート、リーフと呼んでいます。
  • ノード (= 節)
  • ブランチ (= 枝)
  • ルート (= 根)
  • リーフ (= 葉)
特に、最上位の根にあたるノードをルートノードといい、 最下位の葉にあたるノードをリーフノードや葉ノード という呼び方をします。
B木の説明
B木も上記の木構造の一種であるため、木構造と同じ言葉や概念があります。
  • 最上層ノードをルートノードと呼ぶ。
  • 最下層のノードをリーフノードと呼ぶ。
  • ノード同士がそれぞれ繋がり、それぞれにデータ値を持っている。
例として、B木の格納例を示します。 1, 2, 3, … ,9, 10のような単純な数値データをB木へ格納すると、以下のようになります。 数値データは、ルートノード、内部ノード、リーフノードの各ノードに格納されます。 データを検索するときは、
  1. ルートノードから探索を開始します。
  2. 各ノードでの大小比較により、指定された次のノードを辿ります。
  3. 目的のデータがあるノードに辿り着くと、そのノードで検索が終了します。
※B木自身には、ルートノードからリーフノードまでの高さがどのリーフノードに対しても、 常に同じになるように木を自動で再構築する仕組みがあります。 このとき、データ量を数百、数千万に増やしたとしても、片手で数えられる高さまでしか上がらないようにしてくれます。

B+木の構造

ここからは、本題のB+木の説明です。 B+木は、B木の改良版の木構造であるため、B木の基本的な構造を受け継いでいます。 しかし、B木と比べて以下の違いと特徴があります。
  • データ値は、リーフノードのみに格納する。
  • リーフノード以外のノードには、キーを格納する。
  • リーフノードの隣接間がポインタで相互接続される。
B+木もB木と同じく、ルートノード、内部ノード、リーフノードで構成されます。
  • データベースのデータ値を格納しているのは、最下層にあるリーフノードのみ。(→ データ部) ※リーフノード以外のノードには、データ値を格納しない。
  • キー(ポインタ)情報は、内部ノードというノードに格納する。(→ 探索部)
B木で紹介した数値データの格納例をB+木で格納すると、次のようになります。 ※B木は内部ノードにもデータ値を格納するのに対し、B+木はリーフノードのみにデータ値を格納します。 ※内部ノード間同士は、ポインタで接続されています。 ※隣接するリーフノード同士は、双方向のポインタで接続されています。 SQL実行時、データベース(InnoDB)内部では、
  1. ルートノードからデータ探索を開始します。
  2. 探索部にある内部ノード(探索部)をキー情報でリーフノード(データ部)まで探索します。
  3. 最下層にあるリーフノードにたどり着きます。
  4. リーフノード上にあるデータ値を取り出します。
という手順を踏むことで、検索データ値を取り出すことができます。 さらに、隣接するリーフノード同士がポインタで接続されていることから、 隣接リーフノードを順次にたどることでも、値を取得することができます。

なぜB+木が採用されているのか

なぜB+木が採用されているのか、B+木のメリットは大きく分けて2つあります。
  • 等価検索の処理時間が短縮される。
  • 特に範囲検索が高速になる。
検索時間の短縮
(A)B+木を用いない順読み検索と、(B)B+木を用いた検索 にかかる検索時間Oをそれぞれデータ量をnとして、次のように表現します。
  • (A) O(n)
  • (B) O(log n)
以下に、グラフの横軸をデータ量n、縦軸を検索時間Oとした、(A)と(B)2つのグラフを用意しました。 データ量nを増やしていくと、(A)では、データ量nに比例して検索時間Oが長くなります。 しかし、(B)ではデータ量nが増えても、検索時間Oが緩やかにしか上がらないことが分かります。 上記からデータ量が急激に増えたとしても、(B)B+木の方が安定して効率的に検索できることがわかります。 ここで安定・効率的となるのは、ルートノードからリーフノードまでの高さが、
  • すべてのリーフノードにおいて常に同じになる。
  • 全体の木の高さ自体が低い。
というB木の基本構造の恩恵を受けているからです。
範囲検索の高速化
B+木は、B木には持っていない以下の特徴がありました。
  • リーフノードのみに値を格納する。
  • リーフノードの隣接間が接続されている。
これは、リーフノードがソートされている状態でデータが格納されていることかつ、 隣接間のポインタ接続が有効に働くことで、左から右、もしくは右から左へとリーフノードを辿るだけで、 データ値を順番に取り出すことができるということを意味しています。 このため、 WHERE C BETWEEN A AND B や、 WHERE A <= C AND C <= B のような範囲検索時に効果を発揮します。

B+木の挙動

B+木のインデックスの検索の流れとして、以下のSQLを例示します。
等価検索
[SQL] SELECT col FROM table WHERE col = 6; [手順]
  1. col = 6を探します。
  2. 内部ノードをたどります。
  3. リーフノードに到達します。
  4. 値を取り出します。(col = 6)
 
範囲検索1
[SQL]

SELECT col FROM table WHERE col BETWEEN 4 AND 7;

[手順]
  1. col = 4を探します。
  2. 内部ノードをたどります。
  3. リーフノードに到達します。
  4. 値を取り出します。(col = 4)
  5. 次のリーフノードの値を取り出します。(col = 5)
  6. 次のリーフノードの値を取り出します。(col = 6)
  7. 次のリーフノードの値を取り出します。(col = 7)
※左から右へと次のリーフノードを辿り、次のリーフノードの値col = 7になるまで、値を取り出しし続ける。
 
範囲検索2
[SQL]

SELECT col FROM table WHERE col < 9;

[手順]
  1. col = 8を探します。
  2. 内部ノードをたどります。
  3. リーフノードに到達します。
  4. 値を取り出します。(col = 8)
  5. 前のリーフノードの値を取り出します。(col = 7)
  6. ~ 省略 ~
  7. 前のリーフノードの値を取り出します。(col = 2)
  8. 前のリーフノードの値を取り出します。(col = 1)
※右から左へと前のリーフノードをたどり、前のリーフノードがなくなるまで、値を取り出し続ける。

まとめ

  • InnoDBのインデックスの実装には、B+木が利用されている。
  • B+木はB木の改良型のツリー構造をしている。
  • データベースのデータ値は、B+木の最下部にあるリーフノードのみに配置する。
  • 検索時は、内部ノードのキーを検索しリーフノード上のデータを取得する。
  • B+木を利用すると、B木の特性を生かした等価検索のパフォーマンスや、 B+木の特性であるリーフノード同士がポインタで結ばれるため、範囲検索での探索効率も高い。

インデックスの種類

前章では、B+木の基本構造について説明しました。 実際のテーブルのデータがインデックスとして格納されるとき、
  • クラスタインデックス
  • セカンダリインデックス
  • カバリングインデックス
  • 複数インデックス
という名称がついたインデックスに格納されます。 これらのインデックスは、すべて前章で説明したB+木がベースとなって実装されています。 それぞれのインデックスの種類・役割について説明します。 また、各インデックスの説明時には、以下を例示テーブルとして共通使用します。 [例示テーブル] SAMPLE_TABLEというテーブルに、次のカラムが定義されているものとします。

CREATE TABLE SAMPLE_TABLE( id INT NOT NULL PRIMARY KEY, name VARCHAR(100), qty INT, date DATE );

クラスタインデックス

クラスタ化インデックスとも呼びます。 クラスタ(Cluster) = 集団、房 という意味です。 カラムの全データが集まっていると考えます。 CREATE、ALTER文などで、PRIMARY KEYやUNIQUEキーの定義を行ったとき、 そのカラムは自動的にクラスタインデックスとなります。 B+木の各内部ノードには、主キーやユニークキーが割り当てられ、 リーフノードには、主キーを含めたすべてのカラムのレコードのデータが入っています。 セカンダリインデックスでデータが見つからなかったとき、 セカンダリインデックスから渡される主キーで、クラスタインデックスにアクセスしてデータを取得します。

セカンダリインデックス

セカンダリ(Secondary) = 第2の という意味です。 クラスタインデックスとは異なり、特定のカラムデータにつけるインデックスです。 ここで特定のカラムとは、主キーやユニーク以外のカラムを指します。 B+木の各内部ノードには、特定のカラムのインデックスがキーとして割り当てられ、 リーフノードには、主キーが格納されます。 インデックスのデータ探索は、まずこのセカンダリインデックスから行われます。 セカンダリインデックス内に対象検査データが存在しない場合、 セカンダリインデックスの主キーをクラスタインデックスに渡し、クラスタインデックスでの探索を開始します。 CREATE、ALTER TABLE文でインデックスを追加することができます。 次のSQL例は、nameカラムにインデックスを付与しています。

CREATE TABLE SAMPLE_TABLE( id INT NOT NULL PRIMARY KEY, name VARCHAR(100), qty INT, date DATE, INDEX INDEX_NAME(name) );

ALTER TABLE SAMPLE_TABLE ADD INDEX INDEX_NAME(name);

上記で追加したインデックス(nameカラム)は、セカンダリインデックスに配置されます。

複合インデックス

マルチカラムインデックスとも呼びます。 インデックスは、同一のテーブルに1つのカラムだけではなく、複数のカラムにインデックスを持たせることができます。 複合インデックスとは、2つ以上のカラムを組み合わせて、1つのインデックスとすることを指します。 主に2つ以上のカラムに対する検索時に、その全カラムに複合インデックスが付与されていると、検索が高速になります。 複合インデックスでは、例示テーブルの一部を以下のように変更します。 idが1~6に該当するnameカラムの値をすべて「机」に変更しました。 ここで、nameとqtyカラムに複合インデックスを付与します。 次のSQL例で、nameとqtyカラムを複合インデックスとすることができます。

ALTER TABLE SAMPLE_TABLE ADD INDEX INDEX_NAME_QTY(name, qty);

上記のように複合インデックスを付与させると、次のようなWHERE検索が高速化します。 WHERE name = ‘机’ AND qty = 12; しかし、次のようなWHERE検索は、dateカラムにインデックスが付与されていないため、大きな高速化は望めません。

WHERE name = '机' AND date = '2019/12/25';

カバリングインデックス

カバリング(Covering) = 網羅 という意味です。 インデックスでのデータ検索は、セカンダリインデックスとクラスタインデックスが 次の手順を経ることで、データを取得します。
  • 検索対象カラムがセカンダリインデックスに存在しないとき セカンダリインデックス ↓ クラスタインデックス ※セカンダリインデックスから渡された主キーをもとに、クラスタインデックスで検索データを見つける。
  • 検索対象カラムがセカンダリインデックスに既に存在するとき セカンダリインデックス ↓ 検索終了(クラスタインデックスにはアクセスしない)
ここで、カバリングインデックスとは、後者のようにクラスタインデックスにアクセスせず、 検索したいデータが既にセカンダリインデックスのみで取得できている状態のことを指します。 カバリングインデックスでは、クラスタインデックスへのアクセスが省かれるので検索時間が短く済みます。 カバリングインデックスとするためには、SELECTで抽出するカラム、WHEREで検索するカラムなどが それぞれセカンダリインデックス、クラスタインデックスのどちらに格納されているかを意識します。 以下にセカンダリインデックス、クラスタインデックスがどのように協調してデータを検索しているかを示すとともに、 カバリングインデックスとなる実例も併せて紹介します。 ※name, qtyカラムには、予めインデックスを付与している状態とします。
カバリングインデックスとなるSQL例
セカンダリインデックスのみでデータの取得が完結するSQL例です。

SELECT id, name, qty FROM SAMPLE_TABLE WHERE name = '袋';

SELECT name FROM SAMPLE_TABLE WHERE qty = 6;

SELECT id, qty FROM SAMPLE_TABLE WHERE id = 8;

カバリングインデックスとならない例
セカンダリインデックス → クラスタインデックスでデータを取得するようなSQL例です。

SELECT date FROM SAMPLE_TABLE WHERE name = '袋';

SELECT * FROM SAMPLE_TABLE WHERE id = 8;

SELECT id, name FROM SAMPLE_TABLE WHERE date = '2018/5/29';

まとめ

  • テーブルの全データは、クラスタインデックスというインデックスに保持される。
  • セカンダリインデックスは、明示したカラムのインデックスが保持される。
  • セカンダリインデックスのみ、クラスタインデックスのみで検索データの取得が完了することを、カバリングインデックスという。
  • 検索パフォーマンスを上げるには、カラムに必要な分だけ複合インデックスを付与し、適切なSELECT、WHEREを意識する。
Pocket