Oracleってつけましたけど、RDBなら必須の知識ですね。
今日はインデックスについて書いていきます。
効果的なインデックスの張り方ですね。
■インデックス(Index)って？
インデックスの何が重要なのか。
現実世界の辞書で考えて見ましょう。
『日本国語大辞典』（小学館）は実に50万語の文字が載っているとのことです。
この辞書を使って例えば
【インターネット】
っていう単語を調べるとします。
このときどう調べますかね。
辞書は大抵50音順に並んでいるので「い」を探してページを探すと思います。
これがRDBにもあるわけです。
そのテーブルに対して、インデックス(索引)を設定し、その順番で整理しておくことで、
探すときに探しやすくします。
■インデックスの効率的な貼り方
で、この索引の張り方が結構重要です。
ただ決められたルールで並べることをインデックス貼るといったりしますが、
何でもかんでもインデックスを貼ればいいというわけではありません。
例えばさっきの辞書の例。
50音順に並んでいるので探しやすいです。
これがもし「文字数順」に並んでいたらどうでしょう。
同一文字数での並び順が50音順に並んでいたら7文字の場所を探して「い」から始まるところを探します。
これなら何とか探せそうです。
でも「文字数順」で並べた上で「画数」順に並んでいたら？
結構探すのが大変そうです。
「アルファベットに置き換えたときの文字数順」に並べてある辞書とか出していたらその出版社は多分つぶれていますよね
このように何順で並べ替えるかと言うのは現実世界でも重要なわけです。
現実世界で人間にとって「いい並び順」もいうのは、もちろん人間が調べるので人間に対してのわかりやすさです。
RDBの場合パソコンにとって「いい並び順」に並べてあげる必要があります。
このときに意識したいのは「カーディナリティ」という概念です。
「その概念で並べ替えたときにどれだけの種類になるか」
というものですね。
これは「高い」「低い」であらわします。
例えばさっきの辞書。
もし「カタカナor漢字orひらがな」をインデックスにした場合、カーディナリティは3で低いです。
「日本語表記した場合の頭文字」で分けた場合(いわゆる50音順)、濁点除きだと48とかになるので3よりも高めです。
このカーディナリティが高いほうが一般的に検索は早いです。
50万語が載っている辞書の場合「カタカナor漢字orひらがな」の場合、こんな感じになります(なんとなくひらがなと漢字が多そうなのでこんな感じ)。
【インターネット】を探す場合カタカナの箱の10万単語から探す必要があります。
「日本語表記した場合の頭文字」の場合、「い」の箱に入っている1万単語の中から探します。
この場合「日本語表記した場合の頭文字」のほうが効率よさそうですね。
カーディナリティが高いものでインデックスを貼ったほうが効率はよさそうです。
でもこのカーディナリティが高ければいいかというとそういうわけではありません。
「画数」をインデックスにした場合、
駅名で「南阿蘇水の生まれる里白水高原駅」という駅があり、106っぽいです(姓名判断につっこんでカウントしました)
なので1～106まで（もっと多い画数の名詞もあるのかな？）の箱ができます。
地名で「愛知県海部郡飛島村大字飛島新田字竹之郷ヨタレ南ノ割」という長い単語もあるみたいです。
が、1画～106画の箱を作ってもものすごい偏りがあるでしょう。
結局多くの単語が入っている箱ができてしまい、106画の箱には1単語しかはいっていません。
106画の単語が来たら1個しか入っていないので、めちゃくちゃ早く単語を探せますが、
20画くらいの箱は結構内容が詰まってそうです。
このようにカーディナリティが高いものをインデックスに無条件ですればいいかというとそんなことはないよという話でした。
とはいってもカーディナリティが低いものに貼っても意味ない（むしろ邪魔）ので基本は「カーディナリティが高いものにインデックス貼る」が原理原則です
■インデックスを貼る順番
辞書はインデックスに
「50音順」→「50音順」→「50音順」→「50音順」と複数インデックスが貼ってあります。
そのため「インターネット」を探すときは、
「い」行の先頭からではなく「う」行の箱のちょっと「い」行寄りを探すでしょう。
このように複数インデックスをつけることがRDBでもできます。
ただし辞書のように同じものを繰り返しインデックスにするということは基本できません。
例えば
「カタカナor漢字orひらがな」
「日本語表記した場合の頭文字」
の2つをインデックスにするといった具合です。複合インデックスと言ったりします。
わかりやすいように
「カタカナor漢字orひらがな」→3分割の箱を作る
「日本語表記した場合の頭文字」→50分割の箱を作る
とします。
箱を作るためには、一回そのインデックスで並べ替える（ソートする）必要があります。で、切れ目で箱を作っていくわけです（あくまで箱は概念ですが）。
複合インデックスの効果的な貼り方について下に例を交えて説明します。
パターン1
1.「日本語表記した場合の頭文字」
2.「カタカナor漢字orひらがな」
と貼った場合と
パターン2
1.「カタカナor漢字orひらがな」
2.「日本語表記した場合の頭文字」
とした場合はパターン1のほうが効率がいいです。
これは基本的に探す方法がBツリーで検索していくためです。
DBを検索をした際に、DBは内容を並べ替えます。
「インターネット」を50万単語が載っている辞書に対して検索した場合で考えます。
パターン1の場合、
1.まず「日本語表記した場合の頭文字」で50万単語を並べ替える
2.「い」の箱を取り出す→1万単語
3.取り出した1万単語を「カタカナor漢字orひらがな」で並べ替える
4.「カタカナ」の箱約3000単語の中から探す
パターン2の場合、
1.まず「カタカナor漢字orひらがな」で50万単語を並べ替える
2.「カタカナ」の箱を取り出す→16万単語
3.取り出した16万単語を「日本語表記した場合の頭文字」で並べ替える
4.「い」の箱約3000単語の中から探す
4で最終的に探す箱の中身は変わらないですが、この3のところで差がでます。
1万単語を並べ替えるのと16万単語を並べ替えるのでは1万単語のほうが効率がいいです。
そのため、順番は重要ということです。
■カーディナリティが低いものをインデックスにするのはNG
先ほど
カーディナリティが低いものに貼っても意味ない（むしろ邪魔）
と書きました。この理由について簡単に記載します。
インデックスが貼ってある場合上の複合インデックスで説明した通りソートする必要があります。ソートは全部のデータを確認して並べ替える必要があるので結構コストです。
またデータをInsertするときにも若干余計なコストがかかります。
このコストに見合うだけのメリットがあればいいのですが、先ほどのパターン2の場合、1回目の「カタカナor漢字orひらがな」で箱を作っても16万単語の箱しか作れません。この場合、いきなり「日本語表記した場合の頭文字」で箱を作り1万の箱を作ったほうが効率がいいです。
実行環境や利用しているDB(MySQL？Oracle？etc…)によっても中身の動きが違うし、テーブルに入っているデータ量によってもかわってくるのですが、インデックスを貼って遅くなるというパターンもあるのでなんでもかんでも貼ってはいけませんということは認識しておきたいです（Oracleは結構賢くて色々裏で頑張ってくれたりしますが、OracleからMySqlに乗せ換えたら遅くて使い物にならないということもありました。。。Oracleすげぇ)
■効率の良いインデックスを貼るためには
このように、カーディナリティが低いものにインデックスを貼るのは論外です。
ただ、カーディナリティが高いものに無条件で貼ればいいかというとそうでもありません(画数の例)
インデックスを貼ろうとしているものにどんなデータがどんな分布ではいるのかということをしっかり想定して
インデックスは貼りたいものですね。
コメント