# The ART of Indexing(DiDi #05) ## 概要 [[Torsten Grust]]([[Universität Tübingen]])による講義シリーズ「Design and Implementation of DuckDB Internals」(DiDi)第5回のスライド。全22ページ(実質20コンテンツページ)で、[[DuckDB]]が実装する2種類のインデックス、Zonemap(min-maxインデックス)と Adaptive Radix Tree(ART)を扱う。前半でOLAPクエリの全行スキャンが小規模な行部分集合を狙うクエリでは非効率であるという問題設定からZonemapの仕組みと列順序の影響を説明し、後半ではARTの内部構造(ビット列マッピング、span、4種類の内部ノード型、遅延展開・パス圧縮による最適化、探索アルゴリズムの疑似コード)を掘り下げる。 ## 主要メッセージ - OLAPクエリは典型的に全行を読んで集約するが、小規模な行部分集合(あるいは単一行)だけを狙うクエリでは全行スキャンがI/Oとメモリ帯域を浪費する。インデックスはこの無駄を避けるための仕組みである(p.02)。 - DuckDBは自動生成される軽量なZonemap(全列に常在、Sequential Scanの述語プッシュダウンで利用)と、手動作成または制約由来のART(作業メモリを消費し、更新時にメンテナンスが必要)の2階層でインデックスを提供する(p.03)。 - ARTのインデックス利用可否は選択率(selectivity)で判断すべきである。ヒットするrowidがテーブル全体に飛び散っている場合、インデックス経由のアクセスはメモリ局所性を損なう(p.08)。 - ARTの性能はspan(一度に処理するビット数)とノード内表現のトレードオフに支配される。DuckDBはspan=8bit・4種類の可変ファンアウトノード型(Node4/16/48/256)・遅延展開・パス圧縮という組み合わせでこのトレードオフを解決する(p.12-19)。 ## 視覚的に重要な図表 **p.01 タイトルスライド** ![[_attachments/didi-05-the-art-of-indexing/page-002.png]] 講義シリーズ「Design and Implementation of DuckDB Internals」第5回、テーマは「The ART of Indexing」。日付は2026年4月7日、発表者は[[Torsten Grust]]([[Universität Tübingen]])。 **p.06 ARTの構造とインデックスルックアップ手順** ![[_attachments/didi-05-the-art-of-indexing/page-008.png]] 列`c`に対するARTがテーブルとは別に存在し、rowidでテーブル行を参照する構造。ルックアップは「➊rootから入る→➋ARTをリーフノードまでナビゲート→➌rowidでテーブル行にアクセス」の3ステップで完了する。 **p.13 Node4: 内部ノードの基本型** ![[_attachments/didi-05-the-art-of-indexing/page-015.png]] DuckDBはspan=8bitを採用し、非NULL子ポインタ数に応じてNode4/Node16/Node48/Node256の4種類の内部ノード型を切り替える(挿入/削除でオーバーフロー/アンダーフロー時に型変更)。Node4はキー配列(0,2,3,255)と対応する4本の子ポインタを持ち、左から右へ線形探索する。 **p.19 パス圧縮: 悲観的方式 vs 楽観的方式** ![[_attachments/didi-05-the-art-of-indexing/page-021.png]] `duck`・`duct`の2値からなるARTで、単一子しか持たない内部ノード(u→c)を削除する2方式を対比する図。悲観的(pessimistic)方式は削除したノードのバイト列(`uc`)自体を内部ノードに保持してkeyと比較する。楽観的(optimistic)方式は削除したノード数(2)だけを保持し、keyの該当バイトをスキップした上でリーフで値を照合して誤ヒットを排除する。 ## 概念・実体への接続 - [[Adaptive Radix Tree]] — ARTのビット列マッピング、span、4種類の内部ノード型(Node4/16/48/256)、遅延展開・パス圧縮による木高最適化。 - [[Zonemap]] — 行グループ単位の(min,Max)エントリによるSequential Scanのスキップ最適化、列順序がスキップ効果に与える影響。 - [[DuckDB]] — Zonemap・ARTという2階層インデックス設計、`ucol_getSortKey()`(ICUライブラリ)による文字列のバイト列マッピング利用。 - [[B-Tree]] — p.11でARTと二分探索木(BST)の高さ・探索計算量が比較される(横断的知見は[[Adaptive Radix Tree]]側に記載)。 - [[Torsten Grust]] / [[Universität Tübingen]] — 本講義シリーズの発表者・所属。 ## 限界・不確実点 - 公式ページ(https://duckdb.org/library/design-and-implementation-of-duckdb-internals/)のJekyll SEOメタデータでは`datePublished`/`dateModified`がともに`2026-03-19`とされているが、これはコースページ全体(全チャプター一覧)の日付である可能性が高い。本スライドのタイトルページ自体には「April 7, 2026」と明記されており、既存のDiDi #01〜#04と同一の記載パターンである(全チャプターのタイトルスライドが同じ日付を示す点は、テンプレートの日付欄が更新されていない可能性も残る)。出典優先度(スライド > 公式ページ)に従いスライド記載の2026-04-07を`date_published`として採用し、確度は`medium`とした。 - PDF抽出テキストにのみ現れる脚注番号(`#015`〜`#018`)はスライド上のアイコン(クリップボード風マーク)に紐づく社内的な図版IDと見られ、文脈上の意味は不明。DiDi #04にも同種の番号が確認されている。 - p.09の図中に登場するツリー構造・記号(a/n/r等)はPDF抽出テキストでは文字化けするため、画像を正として`and`/`ant`/`any`/`are`/`art`という5値のART例と解釈した。 - p.07脚注1「DuckDB 1.4時点でARTインデックスの占有メモリはbuffer managerの管理下にあるがeviction不可であり、この点を是正する作業が進行中」という記述は、著者の執筆時点(2026年)の開発状況に関する一次情報であり、本スライド以外での裏取りはしていない。 - 音源・動画・transcriptは提供されておらず、口頭説明は反映していない。