インデックスの効果はlogを使わずとも説明できる
データベーススペシャリスト試験とかで「B-tree索引によって計算量が対数オーダーに抑えられる」みたいに言われてあまりピンとこない人、多いんじゃないでしょうか。
まず、「対数」って概念が難しいんですよね。「指数関数的に増える」とはよく言うけど、同じくらい身近なはずの「対数関数的にしか増えない」はあんまり聞いたことがないので、やっぱり難しいんだと思います。
でもインデックスが計算量を削減する仕組みは対数を使わずとも理解できるので、私がいつもラフにイメージしていることを共有してみようと思います。仕組みを理解してラフに直感が働くことは開発上優位に働くことが多いので！
計算量
計算量
= 走査領域のサイズ
= 最悪どのくらい広く走査することになるか？
です。
最悪どのくらい広く走査することになるか？
例を通して理解していきましょう。
例：ユーザーテーブル
| カラム名 | 論理名 | データ型 |
|---|---|---|
id |
ユーザーID | BIGINT |
username |
ユーザー名 | VARCHAR(50) |
address |
住所 | NVARCHAR(255) |
レコード数は仮に6,250,000件とし、次のごくシンプルなSQLの計算量を考えましょう。
# 該当する住所のユーザーを探す
SELECT * FROM user WHERE address = '大分県佐伯市八迫区XX-YY-ZZ';
インデックスが使えない場合
フルスキャンになる場合、走査領域はテーブル全体となり、走査領域のサイズは6,250,000。イメージ的に言うと、北海道稚内市から番地レベルで北から南へ隅から隅まで漏れなく照合していき大分県佐伯市が見つかるまで続けるようなアルゴリズム[1]です。最悪に効率が悪いですね。
走査領域：テーブル全体
インデックスが使える場合
ではaddressにインデックスを貼ったらどうでしょうか。
走査領域：赤の{で示した範囲の和
DBは赤の{で示した領域を上から順になめていきます。４個の{の領域を合わせたものがこのケースの走査領域です。イメージとしては
- 北海道、青森県、...と大分県を特定して47分の1
- 大分県の市町村を走査していき佐伯市を特定して21分の1
- ...
のように、粗く絞り込みながら特定しています[2]。
いわゆる
走査領域のサイズは
これこそ教科書で言うところの「計算量が
まとめ
本文で示した例では、1回の絞り込み毎にカバーできるデータ量が50倍, 50倍, 50倍, ...と指数関数的に広がりました。
計算量が対数オーダーで抑えられるというのは、「計算効率が指数関数的に良い」の言い換えにすぎないということです。対数関数は指数関数の逆関数なので、注目する量をすげかえるだけで指数関数で言い換えることができます。
次に「指数関数的に増加する」というフレーズに出会ったら「じゃあその背後で対数関数的にしか増加しない量はなんだろう？」と、良かったら考えてみてください（面白いですよ）！
Discussion