僕のとにかくシンプルなB-treeインデックスの基礎

この記事について

テーブルの論理設計、SQLの性能問題などDBエンジニアでなくてもDB周りで切っても切り離せない題目といえば、インデックスなわけですが、
僕を含めたもやしエンジニアは無鉄砲に困ったらインデックス、インデックス言いすぎている気がするのでここらで宇宙の全クルーと一緒にインデックスの基礎の基礎を学びなおしてみたいと思います。
インデックス（特にB-treeインデックス）がどういうものか学びなおすことで、どういうクエリがインデックスが効くか効かないかというアプリケーションエンジニアにも身になるところをゴールに持っていければと。

なお、この記事はとにかく簡素にするためにB-treeの説明の前段でAVL木や二分探索木の説明をしたりしません。

筆者も調べながらこの記事を執筆しているので
誤っている点があれば優秀なDBエンジニアの皆様に指摘いただければと思います🙇‍♂️

筆者について

• 社会人歴7年目、IT歴5.5年。（社会人1年目の時はIT業界人とは言えないほど薄くしかITに触れていないかったのでノーカウント）
• 一応、OSS-DB GOLDとかそれなりに難易度高そうな雰囲気のDB系の資格も持ってますが、特にDBエンジニアってわけでもない、ただのアプリケーションエンジニアです。
• 「アプリケーションの出来はDBの出来に9割依存している」「DBを扱える人が一番偉い」という武装派DB原理主義者でもあります。

どうしてB-treeインデックス？

Postgresqlに限らずですが、デフォルトでインデックスに用いられるアルゴリズムの多くはB-treeです。
巷の「こういうSQLはインデックスが効かないので良くない」というご法度もB-treeインデックスを前提に考えられてます。
なのでB-treeを学ぶことはインデックスを理解する上で、非常に大きな意味を持つと思います。

また、さらにそもそものところでB-treeインデックスと明示して先ほどから述べている通り、B-treeじゃないインデックスも存在します。
Postgresqlを例にとるとHashインデックス、GiSTインデックス、GINインデックスとかとか、他の種類のインデックスもあります。

そんな中で、なんでB-treeがインデックスのデフォルトのアルゴリズムになっているかというとB-treeインデックスがホームランバッターじゃないけど打率の高い安打製造機だからです。
いずれかの検索パターンに尖って性能が高いわけではなく、汎用的にいろいろなパターンの検索にそこそこな恩恵をもたらしてくれるインデックス、それがB-treeインデックスというイメージ。

正確にはPostgresqlにはB-treeではなく、B+treeがアルゴリズムとして用いられているようですが、似たようなもんなので、今回はB-treeとして説明を続けます

B-treeってどんなもん？

視覚的にこういうもんと見せた方が分かりやすそうなので、まず視覚的なイメージを示します。

（B-Tree vizualizataionで作成）
感覚的に「これがSQLと絡めて考えたときに大事になりそう」という特徴をいくつか述べますと・・・

• 葉ノード以外はすべて2つ以上の子ノードを持つ。
• M個のキーを持つ節点はM＋1個の子ノードを持つ。
• 葉ノードはすべて同じレベルになる。
• 子ノードには小さい値と大きい値が入り、親ノードには中間値が入る構造になる。
• （親ノードは子ノードを左に小さい値、右に大きい値になるようにぶら下げる）

B-treeを用いた値の検索

極端な例を出した方が理解しやすいと思うので、今回はseq scanで値を検索する場合と比較してみましょう。

seq scan

col = '0012'という検索を行う場合、下記のイメージのように素直に1レコードずつ値を突合しレコードを探すことになります。
12回レコードをチェックして12回目にレコードを特定します。

この検索方法だと
😊レコード数が少なければ、もしくは、所望のレコードが1,2番目など早いタイミングで突合するレコードにあれば、検索は直ちに終わります。
😖検索値によってパフォーマンスが大きく変動します。
😖特に結合の場合に線形に処理時間が増加します。

B-tree を用いたIndex scan

B-treeインデックスを用いたIndex scanの場合は下記のようにTreeをたどり所望の値を検索します。

1. ルートノードの'0008'より大きな値のため、右の子ノードへ
2. '0010'より大きな値のため、右の子ノードへ
   

この検索方法の場合
😊レコード数によらずパフォーマンスが安定します。（後述の終わったインデックスの場合を除いて）
😊高い確率でseq scanのような全量走査よりも短い処理時間で検索が完了します。

インデックスが効かないSQL

B-treeの構造を踏まえたうえでインデックスが効かないSQlとどうして効かないかをいくつか確認しましょう。

インデックスのはられたカラムに対して演算を行っている。

先ほどB-treeの構造を踏まえたうえでと言ったそばから、B-treeが関係ない話で恐縮です。

• 暗黙の型変換
• SQL関数
• 明示的な演算子

といった演算を行っている場合はインデックスというメタな情報が抜け落ちてしまうため、インデックスが効かなくなります。

否定（<>、!=）をつかった検索

例えば、col != '0012'という条件の場合下記の図のように多くのレコードがヒットすることになり、インデックスの恩恵が受けられなくなるため、インデックスが効かなくなります。

is null、is not nullを用いた検索

B-treeはツリーを作る段階でnullを排除するため、インデックスが効かなくなります。
ただ、最近はDBMSによってはis null、is not nullでもインデックスが効くようになったものもあるらしい。

重複した値が多いインデックス

こちらはインデックスが完全に効かなくなるわけではなく、かつ、SQLではどうしようもない領域ですが、極端な例で、下記のように大半が0012のB-treeは、もはやシーケンシャルスキャンでも速度が変わらず、なんならインデックスにアクセスするコストの方が大きくなってしまうことさえあるので、インデックスが効かなくなることがあります。

インデックスは銀の弾丸じゃない

僕も過去のPJで言われたことがありますが、

🧑‍💼 <とりあえずインデックス貼っておいて
🧑‍💼 <とりあえず、ヒント句使ってIndex scanにしとこ

これは、良くないです。

• インデックスをスキャンすること自体がコストが上乗せされる処理です。
• インデックスには当然、構築・更新の処理が必要になるのでタダで使えるもんじゃありません。

（個人的な意見としてはヒント句で実行計画を制御すること自体が個人的には気に食わないですが）

インデックスは用法用量を守って正しく使いましょう。

NEXT

正直自分自身これまであまり触れてこなかった別の種類のインデックスについても調べて記事を書いていけたらと思ってます。