はじめに

私は仕事でRuby on Railsのバックエンド開発をしているのですが、マイグレーションファイルを作成するとき、このテーブルのこのカラムに対してインデックスを貼るべきかどうかで迷うことが多いです。

そもそも、なんでインデックスを使っているのかが完全にわかっていなかったので、何にインデックスを貼るべきがわかりませんでした。

また、すでに運用しているテーブルに新しくインデックスを貼ったら、デプロイでものすごい時間がかかることを見たことがあります。その時に「なんで時間がいっぱいかかるんだろ？」と疑問に思いつつちゃんと理屈を調べていなかったため、今回はインデックスについて原理を含めてなぜ使うのかを理解してみました。

インデックスとは？

そもそもインデックスとはなんでしょう？「貼る」という動詞と一緒に使われているイメージはありましたが、まず実態が知りたいところです。

データベースのテーブルに対する検索速度を向上させるデータ構造

テーブルの特定カラムに対してインデックスを生成するとそのカラムのデータをソートし、別途のメモリ空間に物理アドレスと共にkey valueの形で保存される

なるほど、インデックスというものはDBの中身を元に「ソート」し、メモリの中に入れておくということですね。

「貼る」と表現しているのも、DBとは別で状態をメモリに持つこととなるので、「貼って」おくイメージになると理解できました。

DBは基本的に線形データとしてどんどん保存される仕組みで、以下のように入ってきた順番で並びます。

ここで問題があります。15を探したい時にはすぐ見つかりますが、5を探すためにはこのデータの中身を全部見る必要が出てきます。

例ではデータが8個しかありませんが、もし10万、もしくは10億のデータが存在すると検索するものによっては検索にかかる時間が大きく異なることになります。

また、線形データはデータの不在を検出するためにも全データを見回る必要があります。

インデックスは、以下のようなことができます。

なぜこのようなことができるのでしょう？
以下の図を見てみましょう。

インデックスで出来上がったソートされたデータは一見線形データに見えていてあまり特別な感じがしませんね。

実は、このソートをするためにはよくB+Treeというデータ構造が使われています。
非線形のTreeになっていることで、どんなデータに対しても同じような実行時間でデータを探すことができます。

線形データでは30というデータを探すため、15, 3, 27, 8, 42, 11, 30の7回でデータが見つかるのですが、ツリーだと15, 27, 30の3回でデータを見つけることができます。

同じような理屈で、ツリーは範囲の検索やデータの不在もすぐ見つけることができます。

もちろんですが、データの検索頻度が高いと効率よく使うことができそうです。

また、データの範囲が広いとtreeにまとまったノードを集めるだけでデータの検索ができるので良さそうです。また、ソートされたデータ構造になるため、ソートされて欲しい時にもインデックスを貼った方が良さそうです。

SQLでSELECT句はなぜFINDではないんだろ？と思ったことがありましたが、条件にあったデータを「選択」して上の図のようなソート済みデータを作成するところからSELECTと呼んでいるのかな？と思いました。

今度はB+Treeについてももっと深掘りしていきたいですね~