適応基数木(ART)とトライ系インメモリ索引

なぜトライ系がインメモリ索引で復権したのか

B+Tree はディスク I/O 回数の最小化を最優先に設計された索引です。1ノード=1ページ=1 I/O という対応関係が出発点で、扇出しを大きくして木を低く保つのが眼目でした。ところがデータが丸ごとメモリに載る インメモリDB では前提が崩れます。ランダムアクセスはナノ秒級で、ボトルネックは I/O 回数ではなく CPU キャッシュミスと分岐予測ミス に移ります。

この環境で再評価されたのが、トライ(trie / 基数木)系の索引です。代表格が 2013 年に提案された ART(Adaptive Radix Tree、適応基数木) で、HyPer・DuckDB・Umbra などモダンなインメモリエンジンが採用しています。本稿はその設計判断を B+Tree と対比して解きほぐします。

トライの原理と、その素朴な弱点

トライはキーを バイト列 として扱い、先頭から1バイトずつ枝を辿る木です。深さ d のノードは「キーの d バイト目」で子を分岐します。

• 探索はキー同士の 比較をしない。各階層でバイト値をインデックスに使って子を引くだけで、計算量はキー長 k に比例する O(k)。要素数 N にはほぼ依存しません。
• 共通プレフィックスを持つキーは枝を共有するため、辞書順の 範囲スキャンや前方一致 が自然に効きます。

問題は素朴な実装のメモリ効率です。1バイトは 256 通りなので、各ノードに 256 個の子ポインタ配列を持たせると、子が1〜2個しかないノードでも 256 × 8 = 2048 バイトを消費します。キーが疎なほど空ポインタだらけになり、空間が爆発します。トライが長らく実用索引の主役になれなかった核心はここにあります。ART の貢献は、まさにこの一点を 適応的ノード で解いたことです。

適応的ノード：4種類のサイズを動的に切り替える

ART は内部ノードを、保持する子の数に応じて4種類のレイアウトから選びます。子が増減すると、しきい値で別の型へ 格上げ(grow)／格下げ(shrink) します。

肝は Node48 の工夫です。子が中程度の密度のとき、256 個のポインタを直に持つのは無駄ですが、二分探索のための整列維持も嵌め込みが面倒。そこで「256 バイト分の小さな添字表(各1バイト)」で キーバイト → ポインタ配列の位置 を間接参照します。添字表は 256 × 1 = 256 バイトと軽く、ポインタ本体は実在する子の数(最大48)だけ持てばよい。これにより密度に応じてメモリと探索方式を最適化できます。

パス圧縮と遅延展開：空ノードを消す

適応的ノードだけでは、子が1個だけのノードが鎖状に続く問題が残ります。ART はこれを2つの圧縮で畳み込みます。

• パス圧縮(path compression): 単一子が連続する区間を1ノードに折り畳み、スキップしたバイト列(共通プレフィックス)をノード内に保持します。長いキーでも中間の無分岐部分をノード化せずに済み、木が浅くなってポインタ追跡(=キャッシュミス)が減ります。プレフィックスを各ノードに丸ごと持つ 悲観的(pessimistic) 方式と、固定長だけ持って残りは葉のキーで照合する 楽観的(optimistic) 方式があります。
• 遅延展開(lazy expansion): あるサブツリーに葉が1つしかない間は、内部ノードを作らずに葉を親へ直接ぶら下げます。実際に別のキーが挿入され分岐が必要になった時点で、初めて内部ノードへ展開します。挿入されないキー空間にノードを作らないので、疎なキー集合でメモリが膨らみません。

楽観的パス圧縮ではノード内のプレフィックスが省略されているため、探索の最後に 葉に格納された完全なキーと照合する 検証ステップが要ります。これを怠ると、プレフィックスが偶然一致する別キーを取り違える危険があります。

B+Tree との設計判断の対比

決定的な違いは N への依存性 です。B+Tree の高さは要素数とともに対数で増えますが、ART の高さはキーのバイト長で決まり、10 万件でも 1 億件でも(キー長が同じなら)ほぼ変わりません。一方で ART はキーをバイト列に直せることが前提で、整数や文字列は問題ないものの、複合キーや符号付き整数は 辞書順とキー順序が一致するようバイト符号化 する必要があります(符号付き整数なら最上位ビットを反転させるなど)。この符号化を誤ると範囲スキャンの順序が壊れます。

並行性とまとめ

ART を多コアで使う際の更新には、ロックフリー化を狙った ROWEX や、楽観的読み取りとバージョン番号を組み合わせる Optimistic Lock Coupling が知られます。読み手はノードのバージョンを読んで処理し、最後に再読してバージョンが変わっていなければ整合とみなす方式で、読み取りの大半をロックなしに保てます。

ART の設計を一言で言えば、トライの探索効率を保ったまま、適応的ノードとパス圧縮でメモリ・キャッシュ効率を取り戻した ものです。B+Tree が I/O 時代の最適解だったのに対し、ART はメモリ帯域とキャッシュ階層が支配するインメモリ時代の最適解として位置づけられます。各エンジンがどの索引を選んできたかの歴史的経緯は ストレージエンジンの系統樹 を参照してください。