PostGIS が提供する R-Tree ベースのインデックス

以下を読みながら調べたことをまとめる。個人のメモです。

Postgres の標準の空間の演算子

まずそもそも大前提として、PostgreSQL本体には最初から幾何学データ型（Geometric Types）と、それらを操作するための演算子が組み込まれている。単純な平面座標（XY）としての計算であれば、標準機能だけで十分実用的である。

-- 1. テーブルの作成（標準の幾何学型を使用）
CREATE TABLE locations (
    id SERIAL PRIMARY KEY,
    name TEXT,
    pos POINT  -- 標準の点型 (x, y)
);

-- 2. データの挿入
-- 緯度経度を模した数値を入れることが可能
INSERT INTO locations (name, pos) VALUES 
('東京駅', '(139.767, 35.681)'),
('新宿駅', '(139.700, 35.689)'),
('渋谷駅', '(139.701, 35.658)');

-- 3. インデックスの作成（標準のGiSTが使用可能）
CREATE INDEX idx_locations_pos ON locations USING GIST (pos);

-- 4. 矩形範囲内にある地点を検索
-- 演算子「@>」は「左辺が右辺を包含するか」
-- box('(x1, y1), (x2, y2)') で範囲を指定
SELECT * FROM locations 
WHERE box('(139.70, 35.65), (139.71, 35.67)') @> pos;

-- 5. 指定した地点に近い順に並べる（KNN検索）
-- 演算子「<->」は2点間の距離を返す
SELECT name, pos <-> point(139.767, 35.681) AS distance
FROM locations
ORDER BY distance ASC
LIMIT 5;

-- 6. 円（半径）の中に入っているか判定
-- circle('<(x, y), radius>') で円を定義
SELECT * FROM locations
WHERE circle('<(139.70, 35.65), 0.05>') @> pos;

Postgres の標準インデックス型

さらに、PostgreSQLは、以下のインデックス型を標準提供している。

つまり、extension を使わずとも、R-Treeを内部アルゴリズムに用いる GiST インデックスを作ることは可能である。

-- 1. 点 (point)
-- 内部ロジック: R-Tree (2D MBR)
-- 用途: 単純なXY座標の管理
CREATE INDEX idx_std_point ON table_name USING GIST (pos);

-- 2. 矩形 (box)
-- 内部ロジック: R-Tree (2D MBR)
-- 用途: 範囲エリア、ウィンドウ検索
CREATE INDEX idx_std_box ON table_name USING GIST (area_box);

-- 3. 多角形 (polygon)
-- 内部ロジック: R-Tree (外接する矩形でフィルタリング)
-- 用途: 複雑な形状の境界
CREATE INDEX idx_std_poly ON table_name USING GIST (zone_poly);

-- 4. 円 (circle)
-- 内部ロジック: R-Tree (外接する矩形を使用)
CREATE INDEX idx_std_circle ON table_name USING GIST (radius_zone);

この GiST インデックスは、「多次元データ（空間データ）の包含関係や重なり」 を効率的に処理することができる。例えば、「ある特定の矩形（範囲）の中に含まれる地点を検索したり、複数の図形が重なっている部分を特定したりする場合」 に真価を発揮する。

しかしながら、もし R-Tree を利用したより複雑なクエリを使いたいのであれば、PostGIS extention を使えば良い。

PostGIS extention が提供するもの

1. カラム型

以下の型のカラムを作成できるようになる。

2. インデックス型

上記のカラム型を使って、以下のような応用的な GiST インデックスを作成できるようになる。
⚠️ USING 句で、カラムに入れるべき実データの型を明確にするために: geometry(*, 4326)という形で型を記しているが、実際には入れてはいけない。

CREATE EXTENSION postgis;

-- 1. 基本的な2次元平面図形
-- 内部ロジック: R-Tree (2D MBR)
CREATE INDEX idx_geom_2d ON table_name USING GIST (location: geometry(Point, 4326));
CREATE INDEX idx_area_2d ON table_name USING GIST (boundary: geometry(Polygon, 4326));

-- 2. Z軸（高さ）を含む3次元図形
-- 内部ロジック: R-Tree (3D MBR / 立体的な箱)
CREATE INDEX idx_geom_3d ON table_name USING GIST (location: geometry(PointZ, 4326));
CREATE INDEX idx_area_3d ON table_name USING GIST (building: geometry(PolygonZ, 4326));

-- 3. M値（計測値）を含む図形（路線のキロポストなど）
-- 内部ロジック: R-Tree (次元に応じた箱)
CREATE INDEX idx_route_m ON table_name USING GIST (track: geometry(LineStringM, 4326));
CREATE INDEX idx_full_4d ON table_name USING GIST (sample: geometry(PointZM, 4326));

-- 4. 地球儀ベースの地理座標（球面上）
-- 内部ロジック: R-Tree (Spherical MBR)
CREATE INDEX idx_geog_2d ON table_name USING GIST (location: geography(Point, 4326));

3. クエリの空間演算子

4. クエリの関数

これにより、以下のようなクエリを実行できるようになる。

-- 1. 空間関係の判定 (関係演算子)
-- インデックスを利用して「特定の範囲に含まれるか」を判定
SELECT name FROM stations 
WHERE ST_Intersects(geom, ST_GeomFromText('POLYGON((...))', 4326));

-- 2. 近傍検索 (KNN検索)
-- 特定の地点から近い順に5件取得 (GiSTによる高速化)
SELECT name, geom <-> ST_SetSRID(ST_Point(139.7, 35.6), 4326) AS dist
FROM stations 
ORDER BY dist ASC LIMIT 5;

-- 3. 半径検索 (指定距離以内)
-- 建物Aから半径500メートル以内にある施設を抽出
SELECT * FROM facilities 
WHERE ST_DWithin(geom, (SELECT geom FROM buildings WHERE id = 1), 500);

-- 4. 計測 (距離・面積)
-- 球面(geography)として、2点間の距離をメートル単位で取得
SELECT ST_Distance(geog1, geog2) FROM route_table;

-- 5. 形状の加工と生成
-- 特定の線から周囲10mのバッファ(面)を生成し、その面積を求める
SELECT ST_Area(ST_Buffer(geom, 10)) FROM roads WHERE id = 100;

-- 6. フォーマット変換
-- 内部型を Web アプリで扱いやすい GeoJSON 形式で出力
SELECT ST_AsGeoJSON(geom) FROM markers;

標準提供の R-tree アルゴリズムと PostGIS が提供する R-tree アルゴリズムの違い

以下の通り。

Appendix: そもそも R-Tree とは何か

以下の通り。(ref)