PlanetScaleの記事「B-trees and database indexes」の要約翻訳と補足である。 記事の中心にあるのは、索引の速さを比較回数だけでなく、ストレージとメモリの間で何ページを読み書きするかによって捉える考え方である。
B木がディスク上の索引に向く理由
B木は、一つのノードに複数のキーと値を持つ、平衡した多分木である。 ノード内のキーは順序づけられ、あるキーの左側の子にはそれより小さいキー、右側の子にはそれより大きいキーが入る。 すべての葉が同じ深さにあるため、検索では根から各階層のノードを一つずつたどればよい。
B木は一つのノードを大きくできるので、ノードの大きさをディスクの読み書き単位に合わせられる。 一つのノードに多数のキーを収めると枝分かれの数が増え、数億件を格納しても木を浅く保てる。 木が浅ければ、検索時に読み込むディスクブロックも少なくなる。
B+木がデータベース索引に向く理由
B+木では、実データを葉ノードだけに置き、内部ノードには探索用のキーと子へのポインタだけを置く。 内部ノードが小さくなる分だけ一つのノードに多くのキーを収められ、木を浅くしやすい。
葉ノードは同じ階層に並び、隣の葉へのポインタでつながる。 そのため、一件を探す等価検索だけでなく、ある範囲を先頭から順に読む範囲検索にも適している。
InnoDBの主キー索引と二次索引
InnoDBは、テーブルの行そのものを主キー順のB+木に格納する。 主キー索引の葉には、主キー以外の列を含む行データが置かれる。 この構造はクラスタ化索引と呼ばれる。
二次索引は別のB+木であり、葉には対象列の値と対応する主キーが置かれる。 たとえばメールアドレスに索引を張ったテーブルで次の問い合わせを実行すると、InnoDBは最初にメールアドレスのB+木から主キーを探し、次に主キーのB+木から行を取得する。
SELECT username
FROM user
WHERE email = 'x@planetscale.com';この二段階の検索は、二次索引だけに必要な列がすべて含まれている場合には省ける。 これは被覆索引が速くなりうる理由でもある。
主キーの挿入順序がページ局所性を変える
UUIDv4のような無作為な主キーを追加すると、挿入先の葉は木全体に散らばる。 大量の挿入では多数のページを読み書きし、ページ分割もさまざまな位置で起こるため、キャッシュに収まりにくくなる。
一方、自動採番の整数のような単調増加する主キーは、ほぼ常に木の右端へ追加される。 続けて挿入すると同じ経路とその周辺ページを繰り返し使うため、読み書きするページの種類を抑えやすい。 挿入順と主キー順が一致するので、挿入時刻に近い順で行を読む処理にも局所性が生まれる。
ただし、「UUIDなら常に遅い」という結論にはならない。 UUIDv7の上位ビットには時刻が入り、同時刻内の順序には揺らぎがあるものの、UUIDv4より挿入位置がまとまりやすい。 分散環境で中央の採番器を避けたい、識別子を作成時点で確定したい、識別子を推測されにくくしたいといった要件も、主キー選択に関わる。
主キーの幅はすべての索引に効く
キーが小さければ、一ページに多くのキーを格納できる。 64ビットのBIGINTは8バイト、一般的なUUIDは128ビットで16バイトなので、ほかの条件が同じならBIGINTのほうがB+木の枝分かれを増やし、木を浅くしやすい。
InnoDBでは二次索引の葉にも主キーを保存する。 したがって、主キーが大きいと主キー索引だけでなく、すべての二次索引も大きくなる。 記事が主キーの幅を重視する理由は、この増幅にある。
ページとバッファプール
InnoDBの索引ノードは通常、既定で16KiBのページに対応する。 問い合わせが一行だけを必要としても、ストレージからはその行を含むページ全体を読み込む。
バッファプールは、読み込んだページをメモリに保持するキャッシュである。 必要なページがバッファプールにあればストレージへの入出力を避けられるが、訪問ページ数を減らす意味はなくならない。 ページを探す処理自体に費用がかかり、多くの異なるページを使えば必要なページがキャッシュから追い出されるからである。
記事を読むときの補足
記事の図は、キーの並びと行データの物理的な近さを直感的に結びつけている。 ただし、時刻列による範囲検索の速さは主キーだけでは決まらない。 時刻列に二次索引があれば候補の主キーは連続して読めるが、行本体の取得先は主キー順に散らばる可能性がある。 反対に、必要な列が時刻の二次索引だけでそろえば、主キー索引への追加検索は不要になる。
記事中の「キー、値、子ポインタがすべて8ビットなら、16KiBのノードに682組入る」という箇所は、計算結果から見て8ビットではなく8バイトの誤記と考えられる。 キー、値、ポインタを各8バイトとすれば、一組あたり約24バイトとなり、16KiBを24で割った値は約682になる。 実際のページには管理情報や可変長表現などの費用もあるため、この数は構造を説明するための単純化された例である。
この記事から持ち帰れる判断基準は、「どのキー型が一般に最速か」ではない。 問い合わせと更新がどのページをどの順序で訪問し、その集合がバッファプールにどれだけ残るかを考えることである。