空間インデックス - Wikipedia

空間インデックス（くうかんインデックス、英: spatial index）は、空間データベース（オブジェクト群の空間上の位置などの情報を格納するデータベース）での空間クエリの最適化に使われる。空間データベース以外のデータベースで使うインデックスでは、2点間の距離や複数の地点が問題のエリアにあるかといったクエリに効率的に対応できない。 主な手法[編集] 主な空間インデックス手法としては、次のようなものがある。 グリッド Z階数曲線 四分木 八分木 UB-tree R木: 空間データのインデックスに最適なデータ構造。最小外接矩形 (MBR) を使ってオブジェクト（図形、直線、点など）をグループ化する。オブジェクトを追加する場合、サイズの増大が最小となるMBRに追加する。 kd木 グリッド[編集] グリッド (grid) は、多様体や2次元表面を一連の小さな形状（セル）で充填し、セル単位に識別子