yujiro's blog

「インターネット上で正しい答えを得る最善の方法は、質問することではない。間違った答えを投稿することだ」by ウォード・カニンガム

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 数がめちゃめちゃ多くなる
      • インデックスを貼らないほうがいい。
  • user_id のような外部キー

    • カーディナリティは高い。ユーザー数 = カーディナリティ数 となる。
  • login_type_id のような外部キー

    • ログインタイプが
      • facebook
      • twitter
      • google_plus
      • git_hub
        • とするとカーディナリティは4。カーディナリティは低い。
  • created_at のような Datetime型

    • 秒まで保持していれば、被ることが少ないので、カーディナリティはめちゃめちゃ高い。(はずであるが、MySQL で確認すると、低く出る。参考 : Why does an index on a datetime column have low cardinality in MySQL?
    • ただ、等価評価 で使われることはなく、between 等で使われたり、sort で使われる事が多い。
      • そのため、件数hit 数はめちゃめちゃ多くなる。
        • なので、インデックスを貼る際には第一列にするのは避ける。

ツリー図

以上までが、インデックスを生成するときの基礎的な知識であるが、

カーディナリティが高くて、検索hit 数が低いものから順にインデックスを貼っていくのがセオリー

の理由については、ツリー図をイメージすると理解できる。

例えば、ファーストネーム(first_name)カラムを例にしてみよう。

first_name カラムは、何通りもあるユーザーの色々な名前を保持するから

カラムの値の種類の絶対値

が多く、カーディナリティが高いと言える。

そこにインデックスを貼ると以下のようなツリーが生成される。

f:id:bambookun:20180218133034p:plain

ヘッダブロック、ブランチブロック、リーフブロック の意味については以下を見て欲しい。

ツリーの先頭はヘッダブロックと呼ばれています。ヘッダブロックでは、キー値の 範囲と下層のブロックへのポインタを管理していて、キーの値が指定された場合に、 次にどのブロックを読めばいいかが分かるようになっています。 ブランチブロックはキー値を更に細かく分割して管理しています。キー値が多い 場合はブランチブロックが複数連なります。 リーフブロックは最下層のブロックでキー値とテーブルの行の物理的な位置を 管理しています。又、リーフブロックには前後のリーフブロックへのポインタが 含まれており、<、>、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`);

f:id:bambookun:20180218133100p:plain

複合index については以下に超詳しく、具体的に載っていた。

オトコのソートテクニック2008

複合index について、特に注意するべきで、かつ有名な知識は下記である。

複合インデックスを用いた場合に注意しないといけないのは、最も左端にあるインデックス(left-most index)をWHERE句の検索条件として指定しないと、ソート処理においてインデックスを利用できないという点である。

これは、ツリーをみれば分かるのだが、last_name は first_name の下に順番に並んでいるけど、first_name 全体でみるとバラバラであるためだ。

この状態で、last_name だけでソートをしたり、where で絞りこんでも何も意味がないことがツリーを見れば分かる。

他に複合インデックスを貼る上で注意するポイントとしては、

``left-most index に指定するカラムはカーディナリティが高い(検索hit 数が低いもの)にすべし、という点である。

オトコのソートテクニック にも載っているが、

例えば、全部で100万件レコードがあって、left-most index を使って、where した結果、90万件しか絞り込めませんでした、

という場合、次のindex を使用して90万件をソートしなければいけないよね。

なので、複合index を貼る際は、

> カーディナリティが高くて、検索hit 数が低いものから順にインデックスを貼っていくのがセオリー

ということになる。

上記は誤り。再考します。

参考

オトコのソートテクニック2008

MySQL初級者を脱するために勉強してること -INDEX編- - Qiita

複数列indexの順序と選択性 - Qiita

B-Treeインデックスの話 - Qiita

インデックスの基礎知識

カーディナリティについてまとめてみた

DateTime型の列にインデックスを付けるのは邪道?

Why does an index on a datetime column have low cardinality in MySQL?