B tree index について
MySQL などRDBのインデックスには B tree が採用されている。（厳密に言うと B+tree インデックスである。参考 : B TreeとB+ Treeの違い）
最適なインデックスを生成するには、このツリーの仕組みについて把握している必要がある。
これまで、表面的な知識・ルールしか知らなかったけど、本質から理解しようと頑張ってみる。
間違ってたらコメントください。
カーディナリティ
最適なインデックスを貼る際には、そのカラムのカーディナリティと検索hit 数に気をつける。
カーディナリティ（選択性）とは、
テーブルにカラムがあるとして、カラムに格納されているデータの種類がどのくらいあるのか(カラムの値の種類の絶対値)を、カーディナリティという。
一言でいうと、
カラムの値の種類の絶対値
である。
例えば、性別だったり、削除フラグのような、2つしか種類がないもののカーディナリティは2となる。
性別は男か女、削除フラグは0か1しかデータ（値）の種類がないからである。
一方、user_id みたいな外部キーになるものはカーディナリティは高いと言える。
ユーザー数 = カーディナリティになるから。
もちろん、外部キーになり得るカラムでも、データの種類が少なければ、カーディナリティが低くなる。
検索hit 数
この言い方が適切なのかわからないが、まぁselect でマッチしたレコード数である。
基本的にはカーディナリティと逆の結果になる。
例えば、性別カラムは男、女 しかなく、どっちかにマッチするため、1万レコードあって男女が半々だったら、5000件のhit 数になる。
index を生成する際は、カーディナリティが高くて、検索hit 数が低いものから順にインデックスを貼っていくのがセオリー。
別にセオリーじゃなく、結局は検索とソートの要件による
例
いくつか例を出してみる。
削除フラグのカーディナリティは2（ 0 か 1 ）
- hit 数がめちゃめちゃ多くなる
- インデックスを貼らないほうがいい。
- hit 数がめちゃめちゃ多くなる
user_id のような外部キー
- カーディナリティは高い。ユーザー数 = カーディナリティ数 となる。
login_type_id のような外部キー
created_at のような Datetime型
- 秒まで保持していれば、被ることが少ないので、カーディナリティはめちゃめちゃ高い。（はずであるが、MySQL で確認すると、低く出る。参考 : Why does an index on a datetime column have low cardinality in MySQL?）
- ただ、等価評価 で使われることはなく、between 等で使われたり、sort で使われる事が多い。
- そのため、件数hit 数はめちゃめちゃ多くなる。
- なので、インデックスを貼る際には第一列にするのは避ける。
- そのため、件数hit 数はめちゃめちゃ多くなる。
ツリー図
以上までが、インデックスを生成するときの基礎的な知識であるが、
カーディナリティが高くて、検索hit 数が低いものから順にインデックスを貼っていくのがセオリー
の理由については、ツリー図をイメージすると理解できる。
例えば、ファーストネーム（first_name）カラムを例にしてみよう。
first_name カラムは、何通りもあるユーザーの色々な名前を保持するから
カラムの値の種類の絶対値
が多く、カーディナリティが高いと言える。
そこにインデックスを貼ると以下のようなツリーが生成される。
ヘッダブロック、ブランチブロック、リーフブロック の意味については以下を見て欲しい。
ツリーの先頭はヘッダブロックと呼ばれています。ヘッダブロックでは、キー値の 範囲と下層のブロックへのポインタを管理していて、キーの値が指定された場合に、 次にどのブロックを読めばいいかが分かるようになっています。 ブランチブロックはキー値を更に細かく分割して管理しています。キー値が多い 場合はブランチブロックが複数連なります。 リーフブロックは最下層のブロックでキー値とテーブルの行の物理的な位置を 管理しています。又、リーフブロックには前後のリーフブロックへのポインタが 含まれており、<、>、BETWEENなどの範囲検索がスムーズに行われます。
例えば、Elizabeth というfirst_name をもったユーザーを探すとすると
SELECT * FROM `users` WHERE `first_name` = "Elizabeth";
| ヘッダブロック => | ブランチブロック => | リーフブロック |
|---|---|---|
| A-K => | E-G => | Elizabeth |
と言った具合で検索木（ツリー）が効果的に利用されて検索される。
この検索の流れを踏まえた上で、性別カラムにindex を生成する意味がないことは説明するまでもないだろう。
カーディナリティが低くても、index の生成が効果的な場面もあります
参考 : MySQL(InnoDB)でカーディナリティの低いカラムにINDEXを張る - Qiita
さて、複合index の時はどういうツリーが生成されるのだろうか。
first_name と last_name に複合index を貼った例である。
ALTER TABLE `users` ADD INDEX `multi_index` (`first_name`,`last_name`);
複合index については以下に超詳しく、具体的に載っていた。
複合index について、特に注意するべきで、かつ有名な知識は下記である。
複合インデックスを用いた場合に注意しないといけないのは、最も左端にあるインデックス（left-most index）をWHERE句の検索条件として指定しないと、ソート処理においてインデックスを利用できないという点である。
これは、ツリーをみれば分かるのだが、last_name は first_name の下に順番に並んでいるけど、first_name 全体でみるとバラバラであるためだ。
この状態で、last_name だけでソートをしたり、where で絞りこんでも何も意味がないことがツリーを見れば分かる。
他に複合インデックスを貼る上で注意するポイントとしては、
left-most index に指定するカラムはカーディナリティが高い（検索hit 数が低いもの）にすべし、という点である。
上記図のとおり、複合index において、検索木は第一カラムで作られる。
第二カラム以降の検索は検索木を使えない状態で絞り込みを行うことになるので、
カーディナリティの低いカラムを第一カラムに指定した場合、カーディナリティの高いカラムを第一カラムに指定するのと比べて、
検索木を使わない状態で多くの絞り込みを行うことになるため、パフォーマンスが悪い。
参考
MySQL初級者を脱するために勉強してること -INDEX編- - Qiita
Why does an index on a datetime column have low cardinality in MySQL?
