背景
前回の記事でmysqlのインデックスについてちらっと触れました。
今回はinnoDBのインデックスについて、もう少し突っ込んで調べてみたので、それをまとめます。
B木のアルゴリズムについて
innoDBではインデックスのアルゴリズムにB木が採用されています。
B木は節が最大m個（m>=2）の子を持つことができる木構造で、いわゆる二分木を一般化したデータ構造です。
B木は以下の条件を満たします。
- 根は葉であるか、2〜m個の子を持つ
- 根、葉以外の節はm/2以上の最小の整数〜m個の子を持つ
- 根から全ての葉までの経路の長さが等しい
まずは簡単なB木の構造を見てみましょう
節は最大m個の子へのポインタとm−１個の「境目を表す値」を持ちます。
例えば節Aは2つの子を持ち、その子の境目の値10を持っています。
次に節Bは4つの子、境目の値として3,6,9を持ちます。
同様に節Cは3つの子、境目の値として14,18を持ちます。
次に葉はkeyとvalueを持ちます。葉の定義については諸説あるそうで、
- 枝がすべて終端記号となっているものが葉
- keyが0個の子が葉
などあるそうです。今回の例では前者の定義を用いています。
例えば葉Dはkeyに2を持っています。図には書いていませんが、当然valueも持っています。
ではこの例を用いて探索を行う場合の動きを追ってみます。
例えばkey = 2を探索する場合、まず節Aでkey = 2と境目の値10との大小を比較します。key = 2は当然10より小さいので節Bへとたどっていきます。節Bでも同様にkey = 2とそれぞれの境目の値との比較を行い、該当する子へとたどっていきます。key = 2は3よりも小さいので葉Dへとたどります。
そしてたどり着いた要素が葉である場合、その葉のkeyと検索対象のkeyの比較を行います。葉Dのkeyは2で、今回の検索対象と一致します。よって探索成功となり、葉Dへのポインタを返します。
B+木のアルゴリズムについて
さて、ここまでB木のアルゴリズムを見てきましたが、厳密に言うと、実際にinnoDBで採用されているのはB+木というアルゴリズムです。
B木は全データの順次処理を苦手としています。例えば葉Dまで辿ったら、節Bに戻って葉Eを辿り、節Bの持つ子をすべて辿ったら次は節Cをたどる必要があります。故に再帰などが必要になり、パフォーマンスに影響を与えかねません。
この問題を解消すべく、B+木では、葉が次の葉へのポインタを持つデータ構造となっています。
このように葉の持つポインタをたどることで、容易に全データをたどっていくことが可能となります。
innoDBのインデックスについて
さて、では実際innoDBではどのようなインデックスをどのように使っているのでしょうか。
インデックス
まず、インデックスとはテーブルの中の各レコードを一意に指定できる要素を指します。キーとも呼びます。
クラスタインデックス
innoDBはクラスタインデックスを持ちます。クラスタインデックスとは主キーのシノニム(別名)です。PRIMARY KEYで設定する要素のことですね。
例えばユーザの情報を管理するテーブルがあったとします。
mysql> CREATE TABLE users
-> (
-> id INT(11) NOT NULL AUTO_INCREMENT,
-> first name VARCHAR(64),
-> last name VARCHAR(64),
-> address VARCHAR(64),
-> PRIMARY KEY (id)
-> );
この時、idを主キーとして設定しました。すると、このidをクラスタインデックスとしてB+木を作成します（クラスタ化）。先ほどの図の数字がそのままこの例のidの値を表しているとすると、それぞれ葉には対応するレコードのデータ(first nameとかlast nameとかの情報)が格納されることになります。
クラスタインデックスは主キーのシノニムであるため、テーブルにおいて１つしか作成できません。
なお、主キーを定義しなかった場合、innoDBはNOT NULL制約がついている一意なインデックスをクラスタインデックスとして使用しようとします。それもできない場合、隠れた主キーを自動で定義し、その主キーを用いてクラスタ化します。
なおクラスタ化にはデータ検索の高速化以外にもメリットがあります。
- 関連するデータを近くに配置することができるため、関連するデータの取得の際、ディスクI/Oを減らすことができる
なるほど、主キー（クラスタインデックス）を用いた検索は高速に行えそうですね。しかし、主キーを使用しないデータ検索はどのように行われるのでしょうか。
セカンダリインデックス
セカンダリインデックスは主キーでないインデックスのことです。このセカンダリインデックスを用いてデータ検索を行うことができます。
セカンダリインデックスを用いたデータ検索は、B+木を２回検索する必要があります。
その２回とは以下の通りです。
- 検索対象のデータの主キーの検索
- 主キーを用いた対象データの検索
例えばfuga.comのメールアドレス（セカンダリインデックス）を持つユーザの名前を検索する場合。
まずはじめにセカンダリインデックスであるメールアドレスにより構成されたB+木を辿り、該当するデータの主キーを検索します。そして取得した主キーの値を持って、クラスタインデックスであるidにより構成されたB+木を辿り、該当するデータの検索を行います。計算時間としては、クラスタインデックスを用いた検索時に比べ、単純に２倍の時間がかかることがわかります。
カバリングインデックス
データ検索の場合、SELECT * FROMの記述による全レコードのデータを取得する検索以外にも、該当するレコードの特定のカラムだけ欲しい、という場合があります。例えば、メールアドレスがfuga.comの人のidだけが欲しいといった感じです。
SELECT id FROM users WHERE address='fuga.com';
この場合、直前の図の、セカンダリインデックスにより構成された主キー検索のためのB+木をたどるだけで検索が完了してしまいます。なぜなら、欲しいのはid = 6という情報だけであり、その他のfirst nameやlast nameなどの情報は一切必要ないからです。結果的に、B+木をたどる回数を減らし、レコード全体のデータのロードをなくすことができるため、計算速度を向上させ、リソースを効率よくまわすことができます。
このように、検索対象となるカラムが全てインデックスであることをカバリングインデックスと呼びます。
インデックスを用いないデータ検索
これは素直に全レコードを読み、該当するレコードを順に探していくことになります。もちろん計算量はオーダーnとなり、インデックスを用いたデータ検索よりも低速となります。
最後に
今回はインデックスについて簡単にまとめてみました。パフォーマンスを考えた時、インデックスの設計が非常に重要になってきますね。今後はこのような部分をしっかり意識して実装していきたいと思います。
参考
http://qiita.com/jooohn1234/items/6c765e87fc0a16f078b3
http://nippondanji.blogspot.jp/2010/10/innodb.html
http://www.ei.fukui-nct.ac.jp/~t-saitoh/mt/2010/01/bb.html