B+tree（実際の DB 実装）

30 歳から 50 歳までを取るのに、木を辿り直す

索引で 1 件を引くのは速い。では「30 歳から 50 歳までの会員を全部」はどうでしょうか。

節にも値の実体が置いてある木では、30 歳の行を見つけたあと、次の 31 歳がどこにあるかは分かりません。木のどこかにあるとしか言えないので、また根から辿り直します。該当が 5 万件あれば、5 万回辿り直すことになります。1 件ずつなら速いのに、範囲になった途端に割に合わなくなります。

実際の DB が使っている B+tree は、ここを 2 つの工夫で解いています。

内側の節は、道しるべだけにする

1 つ目は、値の実体を葉だけに置いたことです。内側の節に残るのは「ここから先は 30 以上」といった境界の値だけになります。

これは節約として効きます。1 つの節の大きさは決まっているので、実体を追い出したぶん、境界の値をもっと詰め込めます。詰め込めるほど 1 段で分かれる数が増え、木は浅くなります。代わりに、どの値を探しても必ず葉まで下りることになりますが、下りる段数自体が減っているので割に合います。

2 つ目は、葉と葉を横につないだことです。

こうなると、範囲の取り出しは「木を 1 回だけ下りて、あとは横に歩く」で済みます。しかも横に並んだ葉はディスク上でも近くにあることが多いので、飛び飛びに読むより速く読めます。木を辿り直す回数は、最初の 1 回だけです。

つながりは双方向なので、新しい順に取り出したいときは右端から左へ歩けます。並べ替えの指示を書いても、すでに並んでいるものを順に読むだけで済み、全部取り出してから並べ直す作業が発生しません。索引の並び順と、画面に出したい順が一致していると得をするのはこのためです。

全部の列を取りに行くと、索引を 2 回引く

もう 1 つ、実装の側の話があります。MySQL の InnoDB では、主キーの索引の葉に行そのものが入っています。主キーで引くときは、木を 1 回下りればもう行が手に入ります。

主キー以外の列に貼った索引は違います。葉に入っているのは行そのものではなく、主キーの値です。メールアドレスで検索すると、まずその索引を辿って主キーを得て、次にその主キーで主キー側の木をもう一度下ります。2 段構えです。該当が 1 万件あれば、この往復も 1 万回起きます。必要のない列まで含めて全列を取りに行けば、この往復は必ず発生します。逆に、欲しいものが主キーだけなら往復は起きません。

だから一覧を作るときは、返す件数と取る列を先に決めます。1 画面に 20 件しか出さないのに 1 万件を取ってからアプリ側で切ると、往復も 1 万回起きます。

主キーの選び方にも影響します。値がばらばらな主キーを使うと、新しい行が木のあちこちに挿し込まれ、そのたびに節の分割が起きます。時間順に増える主キーなら、追加は木の右端に集まるので分割がほとんど起きません。なお PostgreSQL は本体を別に持つ構造で、主キーの索引も他の索引と同じ扱いです。どちらにせよ長く運用すると節に隙間が溜まっていくので、索引を作り直す定期作業が必要になります。