# 多次元索引 ## 定義 多次元索引(multidimensional index)とは、複数の列(次元)に対する範囲クエリを同時に効率よく評価できる索引構造である。最も一般的な複数列索引である concatenated index(複数フィールドを連結して1つのキーにする索引。姓→名の電話帳が典型例)は、先頭フィールドまたは先頭からの複合一致でしか有効に使えず、2番目以降のフィールド単独での検索には使えない。これに対し多次元索引は、緯度・経度のように「どちらの軸でも独立に絞り込みたい」複数属性を同時に扱える。代表的な実装は空間充填曲線(space-filling curve)で多次元座標を1次元数値へ変換し通常の B-Tree を使う方法と、*R-Tree* や *Bkd-Tree* のように近接するデータ点を同じ subtree にまとめる専用の空間索引がある。PostgreSQL の Generalized Search Tree(GiST)索引機能を使い R-Tree を実装する PostGIS が代表例である。用途は地理空間データに限らず、(red, green, blue)のような色空間の3次元索引や、(date, temperature)のような2次元の観測データ索引にも一般化できる。(Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 4 Storage and Retrieval]] "Multidimensional and Full-Text Indexes") ## 横断的知見 - 現時点では単一ソースからの導入であるため、複数ソースを突き合わせた横断的知見は未蓄積である。多次元索引が解決する「複数属性の同時範囲クエリ」という問題設定は、[[Zonemap]]・[[Adaptive Radix Tree]]が扱う単一列(または列順序に依存する)索引の絞り込みとは異なる軸であり、今後これらの概念との対比を追記する余地がある。(Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 4 Storage and Retrieval]]) ## 未解決の問い - 空間充填曲線による1次元化とR-Tree/Bkd-Treeのような専用構造は、挿入・更新頻度やクエリの選択性によってどちらが有利になるか。DDIA第4章はどちらも紹介するが定量比較はしていない。 - 正方形・六角形の規則格子(H3等)による空間索引は、R-Treeベースの索引と比べてどのようなトレードオフ(索引サイズ・更新コスト・境界をまたぐクエリの扱い)を持つか。 - 多次元索引と[[ベクトル検索インデックス]](高次元埋め込みベクトルの近似最近傍探索)は、次元数が増えるにつれて「次元の呪い」により通常のR-Treeが機能しなくなる点で連続している。R-Treeが実用的に機能する次元数の上限はどの程度で、その上限を超えた領域でIVF/HNSWのような近似索引に切り替える設計上の目安はあるか。 ## 関連 - ソース: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 4 Storage and Retrieval]] - 概念: [[B-Tree]] / [[ベクトル検索インデックス]] / [[転置インデックス]] - エンティティ: [[PostgreSQL]] ## 出典 - [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 4 Storage and Retrieval]](§Multidimensional and Full-Text Indexes — concatenated index、空間充填曲線、R-Tree、Bkd-Tree、PostGIS/GiST)