# Adaptive Radix Tree ## 定義 Adaptive Radix Tree(ART)は、値のビット列表現に基づいて自己組織化する順序付き探索木であり、値をハッシュ化・比較しない索引構造である。key の先頭から `s` ビットずつ(span)区切り、各深さでその `s` ビット断片を使って子ノードへ降りる。DuckDB では `CREATE INDEX` の DDL、または `UNIQUE`・`PRIMARY KEY`・`FOREIGN KEY` 制約宣言時に暗黙的に単一列(または複合列)の ART が作成され、テーブルストレージとは別にメンテナンスされる(作業メモリを消費し、更新のたびに保守コストが生じる)。ART の木高は保持するエントリ数 `n` ではなく値のビット長 `k` にのみ依存し、`⌈k/s⌉` 段の内部ノードを持つ。探索・挿入の計算量は O(k) である。(Source: [[@2026__DiDi__The ART of Indexing]]) DuckDB は span `s = 8` bit(1バイト)を採用し、非 NULL 子ポインタ数に応じて Node4・Node16・Node48・Node256 の4種類の内部ノード型を切り替える可変ファンアウト設計を取る。Node4/Node16 はキー配列と子ポインタ配列を線形または SIMD 探索で対応付ける小規模ノード、Node48 はキーバイトを 256 要素のインデックス配列で `@0..@47` の子ポインタ添字に変換する中規模ノード、Node256 はキーバイトをそのまま子ポインタ配列の添字として使う大規模ノードである。挿入・削除に伴うオーバーフロー/アンダーフローでノード型を動的に変更する。加えて、単一子しか持たない内部ノードを取り除く遅延展開(lazy expansion)と、値をまだ確定しない共有プレフィックスを圧縮するパス圧縮(path compression、悲観的/楽観的の2方式)により木高と空間使用量を削減する。(Source: [[@2026__DiDi__The ART of Indexing]]) 値をビット列にマッピングする規則は型ごとに定義される。符号なし整数は標準的な二進表現(リトルエンディアン機ではバイト順を反転して MSB を先頭にする)、符号付き整数は符号ビットを反転してから符号なし整数と同様に扱う、IEEE 754 浮動小数点数は常に符号ビットを反転し、元の符号ビットが立っていた場合はさらに全ビットを反転する。文字列は UTF-8 バイト列を(DuckDB では ICU の `ucol_getSortKey()` により)ソートキーへ変換し、終端記号を付けて他の値の接頭辞にならないようにする。複合値は各フィールドをマッピングしてから連結する。NULL はビット長 `k` を増やして追加の値として表現する。(Source: [[@2026__DiDi__The ART of Indexing]]) ## 横断的知見 - **ART と B-Tree は「比較ベース vs ビット分解ベース」という異なる軸で木高を縮める**: [[B-Tree]] は key 比較による順序付き探索木であり、探索計算量は `O(k·log₂(n))`(`k` は値のビット長、`n` はエントリ数)である。一方 ART は値を比較せずビット列の共通接頭辞で分岐するため、木高は `n` に依存せず `⌈k/s⌉` に固定される。`n > 2^(k/s)` の条件下では ART が BST(および実質的に B-Tree)より低い木高を持つが、これは「インデックスをどう速くするか」という共通の問題に対し、DuckDB が Zonemap(スキャンの絞り込み)・ART(点/範囲探索)という異なる粒度で対処している設計判断の一部として理解できる。(Source: [[@2026__DiDi__The ART of Indexing]]) - **ART の性能はメモリ局所性とのトレードオフを内包する**: 選択率(selectivity)`sel(p)` が低い場合にのみ ART 経由のアクセスは有利になる。ART のリーフが指す rowid はテーブル全体に散らばりうるため、ヒット件数が多い述語では ART 経由アクセスがメモリ局所性を損ない、[[Zonemap]] を用いた Sequential Scan による全行スキャンより不利になりうる。この点は Zonemap が「スキャンをどれだけスキップできるか」という粗い最適化であるのに対し、ART が「個別行にどれだけ速く到達できるか」という細かい最適化であるという役割分担を裏づける。(Source: [[@2026__DiDi__The ART of Indexing]]) ## 未解決の問い - p.09 の図中に登場するツリー構造・記号(`and`/`ant`/`any`/`are`/`art` の5値)は PDF 抽出テキストでは文字化けするため、画像を正として解釈した。他ソースでの裏取りは未実施である。 - p.07 脚注1「DuckDB 1.4 時点で ART インデックスの占有メモリは buffer manager の管理下にあるが eviction 不可であり、この点を是正する作業が進行中」という記述は執筆時点(2026年)の開発状況に関する一次情報であり、本スライド以外での裏取りをしていない。是正作業の完了時期や具体的な実装方針は不明である。 - ART の悲観的/楽観的パス圧縮のどちらを DuckDB が実運用でデフォルト採用しているか、また両者の使い分け基準(値の長さ、更新頻度など)はスライドからは読み取れない。 - span `s` を大きくした場合の Node256 の空間コスト(`s=8` で 2kB/ノード)が、より大きい `s`(例: 16 bit)でどこまで許容範囲か、DuckDB の内部でどう検証されているかは不明。 ## 関連 - ソース: [[@2026__DiDi__The ART of Indexing]] - 概念: [[Zonemap]] / [[B-Tree]] - エンティティ: [[DuckDB]] / [[Torsten Grust]] / [[Universität Tübingen]] ## 出典 - [[@2026__DiDi__The ART of Indexing]](ART の定義、ビット列マッピング、span とノード型設計、遅延展開・パス圧縮、探索アルゴリズムの疑似コード)