はじめに
はじめまして。YUZURIHAの渡邉です。
今回はリレーショナルデータベース（以下RDB）のインデックスについて、語っていきたいと思います。
RDBにおいてもっとも重要な知識を一つ挙げよと言われたらなんでしょうか？
私は、それは 「B+Treeのインデックスシステム」 だと答えます。
もし、B+Treeのインデックスが存在していなければ、RDBなんて非効率な仕組みに存在価値はなく、とっくに他のデータベースシステムに置き変わられていることでしょう。
この変化の激しいIT業界において、RDBとSQLが半世紀以上もの間、データベースの中心として使われ続け、そしておそらく今後もそれが続くであろうと思われる理由は、B+Treeという神の恩寵のようなアルゴリズムとRDBの相性が抜群に良いからです。
しかし、私もこの業界にいて久しいですが、RDBのB+Treeインデックスをちゃんと理解して使いこなせる人は少ないと言ざるをえません。
私の経験上、Webアプリケーションのパフォーマンス問題は、結局のところほとんどがDBに起因しており、
そのほとんどは、SQLとインデックスを上手く扱えれば解決できた問題――すなわち、エンジニアのインデックスに対する理解不足に起因していたといっても過言ではありません。
また、SQLとインデックスの工夫で解決できる問題なのに、正規化を崩した変なテーブル設計をしたり、複雑でぶっ飛んだ解決案を実行してコスト増と保守性の低下を招く……といった光景も、何度も見てきました。
B+Treeインデックスは、FullTEXTインデックスやその他のプログラミング学習と違い、仕様を覚えたらだれでも同じように使えるというものではありません。
そのアルゴリズムまで深ぼって理解し、それをいかに応用していくか、というのが重要になります。
その代わり、そのアルゴリズム自体は小難しく考えなくても理解できるものです。
一方で、知識マウントを取ろうと小難しい用語を多用して解説しようと思えばそれもまたできてしまうものでもあり、それが巷での一般理解を敷居の高いものにしてしまったり、誤解をはびこらせている原因にもなっているように思います。
そこで今回は、細かい話は一切排してとにかく単純化してB+Treeインデックスの解説をしていきたいと思います。
これは一般的に思われているよりもはるかに汎用性が広く、奥が深く、そして面白いものなのです。
SQLのアルゴリズムの計算量の話
DBのパフォーマンスについては巷でも色々語られますが、結局のところ 「SQLによって実行されるアルゴリズムの計算量の総和」 に比例すると言ってよく、そのアルゴリズムはざっくり分解すると下記の3つになります。
- 対数アルゴリズム $O(\log_b N)$ ・・・インデックス検索。超速い。
- 線形検索アルゴリズム $O(N)$ ・・・フルスキャン。遅い。
- ソートアルゴリズム $O(N \log_b N)$ ・・・超遅い。
他にもないことはないですが、おまけみたいなもの（暴論）なので気にしなくて良いです。
さらに言えば、ここで登場する計算式は2つしかありません。
$N$ はただの件数ですから、実質 $log_b N$（すなわち対数）だけ理解できれば、SQLの実行速度は概ねイメージできるようになる ということになります。本当です。
※厳密に言えば、インデックスの $log_b N$ とソートアルゴリズムに出てくる $log_b N$ は「底(b)」が違うため値が異なりますが。
対数の話
そこで対数の話です。
この $O(\log_b N)$ で表される数値のことを対数とも呼びます。
ところで、対数ってなんでしょうか？ Wikipediaにはこのように書いてあります。
ある数 $x$ を数 $b$ の冪乗 $b^p$ として表した場合の冪指数 $p$ である。この $p$ は「底を $b$ とする $x$ の対数（英: logarithm of $x$ to base $b$; base $b$ logarithm of $x$）」と呼ばれ、通常は $\log_b x$ と書き表される。また、対数 $\log_b x$ に対する $x$ は真数（しんすう、英: antilogarithm）と呼ばれる。（後略）
……これで理解できますか？
対数を理解するのに、こんな小難しい理屈は要りません。
ものすごくざっくり言ってしまえば、対数とは（その世界における）桁数のことです。
「その世界」のことを「底（てい）」といいます。我々は10進法の世界に生きていますから、我々の世界の底は10ということになります。……あぁ、またややこしくなりかけましたね。とりあえず 「対数 ＝ 桁数」 くらいに考えておけば良いでしょう(暴論)。
この対数の恩恵は、私たちの身近に存在します。それが「アラビア数字」です。
例えば「15」という数字を表すとき、線形検索的な表し方をするとこのようになります。
|||||||||||||||
おそらく最初期の人類はこのように数値を数えていたことでしょう。ローマ数字なんかには少しその名残がありますよね。
これを認識するには「15回数える」という動作が必要になります。これが $O(N)$ の世界です。
一方で、これがアラビア数字（15）だと、わずか2回のステップで認知できるようになります。これが $O(\log_{10} N)$ の恩恵なのです。
15くらいなら良いですが、これが「1億」という数字だったらどれほど恐ろしいことでしょうか？
インデックスを使わない検索というのはこれほど愚かなことをやらせているということです。
B+Tree インデックスの動きをイメージする
もう一つ、例を挙げます。
ここに、完全に書籍IDの順番に並んでいる巨大な図書館があります。
この図書館は、書籍ID10個ごとに区分けがされており、10個の区分けごとに棚一列が割り当てられ、一つの棚は10列によって構成され、10個の棚ごとに小部屋があって、10個の小部屋ごとに中部屋があって……と、10の単位ごとに大きな箱に入っているような構成（蔵書1億冊）だとします。
このような図書館で、あなたがとある漫画の1巻の書籍IDを渡され、「1巻から100巻まで（同じ漫画は巻数で連番が割り振られているとする）を、正確に順番通り取ってきてほしい」と言われたと想像してください。
この場合、歩く労力はともかく、探すための判断はわずか9ステップで1巻にたどり着くことができます。そして、そこからは連続した100回のステップで、順番通りに目的の巻を取得できます。
これがもし、書籍IDが整列していない（インデックスがない）状況だったらどうでしょうか？
すべての書籍を確認しなければいけませんから、最大で1億ステップが必要になります。
そして、 そのあと取ってきた100冊を並び替えしなければなりません。 追加でだいたい700ステップくらいの労力もかかります。
ここでもう一つのポイントがあります
インデックスを使っている例では、並び替え操作って必要なかったですね。
これがB+Tree のもう一つの威力です。B+Treeで取得した結果は必ず順番通りになっています。
順番通りに並んでいるから並び替えがいらないんです。
これが SQL において「インデックスは ORDER BY に効く」といわれる理由です。
ついでに言うと、上に述べたように（同じデータ量のとき）ソートアルゴリズムは線形検索よりも数倍から数十倍も計算量がかかりますから、クエリオプティマイザは ORDER BY 句を重視した実行計画を立てがちで、これがインデックスをうまく理解していない人を惑わせるポイントになっています。
※
今回は10進数で話をしましたが、実際はB+Treeの枝の数は10個固定ではないですし、
深さによって数も変わるので正確に表すと難しい数式になってしまいますが、
些細な話です(暴論)
1億ぐらいの数であれば実際はさらに早いくらいに思っておけば十分でしょう。
おわりに
今回は対数アルゴリズムとB+Treeインデックスのアルゴリズムの概要 について、
具体的なイメージをしてもらいやすいように解説させていただきました。
まずは少しでもデータベースのアルゴリズムの面白さを感じてもらい、B+Tree の理解に興味を持ってもらえれば幸いです。
最後までご覧いただきありがとうございました。