B-tree の仕組み

索引を辿るのに 20 回もディスクを叩けない

並んだデータを速く探す構造なら、二分探索木がよく知られています。1 回の比較で候補が半分になるので、1000 万件でも 24 段ほどで目的地に着きます。段数だけを見れば十分に速い。

それでも DB の索引は二分探索木を使いません。理由は、1 段下りるたびに何が起きるかにあります。

索引はメモリに全部は載りません。大部分はディスク上にあり、必要な部分だけを読み込みます。しかもディスクは 1 バイト単位では読めず、決まった大きさのかたまり単位で読みます。メモリから値を取るのが数ナノ秒なのに対し、この読み込みは SSD でも数十マイクロ秒かかります。桁が 4 つ違います。

つまり 24 段下りるということは、最悪 24 回この待ち時間を払うということです。段数ではなく、ディスクに触った回数が効いてきます。

ディスクがかたまり単位でしか読めないのは、記憶装置の作りの問題で、こちらの都合では変えられません。索引の設計は、この決まりに逆らわない形を選ぶところから始まります。

1 段で 100 通りに分かれる

そこで発想を変えます。1 回読むならどうせかたまりで読むのだから、そのかたまりを目一杯使えばよい。

B-tree は、1 つの節をディスクの読み込み単位と同じ大きさ（16 キロバイト程度）に合わせ、その中に境界となる値を 100 個以上詰め込みます。1 回読むだけで、次に進む先が 100 通り以上に絞られます。

            [ 30 | 60 ]
           /     |     \
    [10|20]   [40|50]   [70|80|90]

上の図は境界が 2 つしかない小さな例です。50 を探すなら、根の 30 と 60 を見て「30 以上 60 未満」の枝へ下り、その中を見て終わりです。実際には 1 つの節が 100 通り以上に分かれるので、1000 万件でも 3 段か 4 段しかありません。ディスクに触る回数が 24 回から 4 回になります。理論上の段数ではなく、この定数の軽さが選ばれた理由です。

実際にはもう少し得をします。根とその次の段は、どの検索でも必ず通るので、ほぼ常にメモリに載ったままになります。ディスクへ取りに行くのは下の 1 段か 2 段だけで、3 段の木だから 3 回待つ、という話にはなりません。

詰まったら、真ん中を上に押し上げる

木の形をした索引には、片側にばかり伸びて段数が増えてしまう心配が付きまといます。B-tree はこれを、決まった手続きで防いでいます。

節が満杯の状態で新しい値が来たら、その節を 2 つに割ります。このとき真ん中の値だけを親へ渡し、残りを左右に分けます。親も満杯なら、親でも同じことが起きます。それが根まで届くと、根が 2 つに割れて新しい根が上にできます。

木が伸びるのは葉の側ではなく根の側で、これが効きます。どの葉も常に同じ深さに揃うので、どの値を探しても掛かる回数が変わりません。削除で節が空きすぎたときは、隣とくっつけるか、値を分け合って埋めます。

この手続きには、外から順番を指示する必要がありません。挿入するたびに、詰まった節が自分で割れていくだけです。形を保つ仕事を、木自身が引き受けています。

なお、実際の DB が使っているのは、値の実体を葉だけに置いた B+tree という変種です。同じ発想を、もう一段だけ押し進めたものになっています。