空間インデックス：R-Tree と Z-order/ヒルベルト曲線

なぜ B+Tree では空間検索が破綻するのか

WHERE lat BETWEEN ... AND lon BETWEEN ... のような 矩形範囲検索（window query） や、「ある点から半径 5km 以内」を考えます。素朴に lat と lon それぞれへ B+Tree を張っても、うまくいきません。

理由は単純で、B+Tree は一次元の全順序（total order）を前提にしている からです。キーは数直線上に一列に並び、範囲検索は「葉リンクを連続して辿る」一回の連続スキャンになります。ところが二次元の点 (lat, lon) には、近さを保つ自然な一列の並びが存在しません。lat で並べれば lon が散らばり、lon で並べれば lat が散らばります。

その結果、lat の索引だけ使うと「緯度は範囲内だが経度は遠い」点まで大量に拾い、フィルタで捨てる羽目になります。二つの索引の結果を突き合わせる（ビットマップ AND）にしても、片側の候補が膨らめば効果は薄い。多次元には「近いもの同士が必ず隣り合う一列」が無い ——これが空間索引が解くべき本質的な問題です。

これに対する答えは大きく二系統あります。多次元のまま階層的に空間を束ねる R-Tree と、多次元を一次元キーへ線形化して既存の B+Tree に載せる空間充填曲線 です。前者は専用構造を作り、後者は既存の索引基盤を流用します。

R-Tree：最小外接矩形を階層的に束ねる

R-Tree は B+Tree を多次元へ一般化した平衡木です。葉に格納するのは個々の空間オブジェクトを覆う 最小外接矩形（MBR: Minimum Bounding Rectangle） で、内部ノードはその子たちの MBR をさらに覆う一回り大きな MBR を持ちます。つまり「矩形を矩形で包む」入れ子になっています。

• 葉ノード：実オブジェクト（点・線・多角形）の MBR とその参照。
• 内部ノード：子ノード全体を覆う MBR と子へのポインタ。
• B+Tree と同様、全葉が同じ深さにある平衡木で、ノードは1ページに対応する。

探索（窓問合せ）はこう進みます。ルートから始め、各エントリの MBR が 問合せ矩形と重なる枝だけ を再帰的に降ります。重ならない枝は、その配下に答えが無いと確定するので丸ごと枝刈りできます。

R-Tree 窓問合せ search(node, Q):
  for each entry e in node:
      if MBR(e) が Q と重なる:        # 重ならなければ枝刈り
          if node が葉:  e を結果候補へ
          else:          search(child(e), Q)   # 重なる枝だけ降りる

ここに B+Tree との決定的な違いがあります。一次元の B+Tree では区切りキーが空間を 互いに素な区間 に分けるため、降りる枝は常に一本でした。R-Tree の MBR は 互いに重なってよい ので、問合せ矩形が複数の子 MBR にまたがると、複数の枝を同時に降りることがあります。重なりが多いほど辿る枝が増え、探索が劣化します。MBR の重なり（overlap）と無駄面積をいかに小さく保つかが R-Tree 性能の核心 です。

分割戦略：R-Tree の品質を決めるもの

ノードが満杯になったときの 分割（split） こそ、R-Tree の良し悪しを決めます。同じ点群でも、分割の仕方で MBR の重なりと総面積が大きく変わるからです。代表的な戦略を対比します。

実務で広く使われるのは R*-Tree です。分割と挿入時に「子 MBR 同士の重なり」と「外接矩形の周長」まで評価関数に入れ、満杯ノードの一部エントリを抜いて挿し直す 強制再挿入 で木全体を整えます。結果として重なりが減り、窓問合せで降りる枝が少なくなります。代償は挿入コストの増大で、これは B+Tree のフィルファクタ と同様、更新負荷と探索効率のトレードオフです。

一方、初期構築時に全データが揃っているなら STR（Sort-Tile-Recursive）一括ロード が強力です。データを一方の軸でソートして縦帯（タイル）に切り、各帯内をもう一方の軸でソートしてページに詰め、それを下から束ねます。隙間なく詰まり重なりも小さい木が一度にできるため、逐次挿入より高品質かつ高速に構築できます。

空間充填曲線：多次元を一次元キーへ線形化する

もう一方の戦略は、専用木を作らず 多次元座標を一次元の整数キーへ写す ものです。この写像に使うのが 空間充填曲線（space-filling curve） で、二次元（以上）の格子を一本の連続した線で隙間なく塗り潰す順序を与えます。各セルにその線上の通過順（曲線距離）を番号として振れば、(lat, lon) が一つの整数キーになり、あとは 既存の B+Tree にそのまま載せられます。専用実装が不要なのが最大の利点です。

良い曲線の条件は 空間的局所性の保存 です。空間で近い二点が、一次元キーでも近い値になってほしい。そうであれば、矩形範囲は「キーのいくつかの連続区間」に対応し、B+Tree の連続スキャンで読めます。局所性が崩れるほど、一つの矩形が多数の細切れキー区間に散らばり、ランダムアクセスが増えます。

Z-order（モートン順序）

Z-order 曲線 は最も実装が軽い線形化で、座標ビットを インターリーブ（交互配置） するだけで一次元キー（モートンコード）が得られます。

Z-order（モートン）コードの作り方（2次元）
  x = b2 b1 b0   y = a2 a1 a0  （各座標を整数ビット列に）
  モートンコード = a2 b2 a1 b1 a0 b0   ← y,x のビットを交互に並べる
  例) x=3(011), y=5(101) → 10 01 11 (2進) = 39

ビット演算だけで双方向に変換でき、四分木のセル番号とも自然に対応するため、実装が極めて簡単です。難点は 局所性の不連続 にあります。曲線が空間を Z 字に塗るため、隣接セルでもブロック境界をまたぐとキーが大きく飛ぶ「長いジャンプ」が生じます。このため一つの矩形が複数のキー区間に割れ、各区間を別々にスキャンする必要が出ます。

ヒルベルト曲線

ヒルベルト曲線 は、常に一つ前のセルと 隣接するセルへ進む（曲線が飛ばない）ように空間を再帰的に塗ります。Z-order のような長いジャンプが原理的に起きないため、空間的局所性が Z-order より高い のが定量的に知られた性質です。同じ矩形を覆うのに必要なキー区間の数が少なく断片化しにくいので、範囲検索がより連続的なスキャンになります。

代償は変換コストです。ヒルベルト座標の符号化・復号は、各ビット段で象限ごとに座標軸を回転・反転させる必要があり、ビットを混ぜるだけの Z-order より計算が重くなります。実装の軽さの Z-order、局所性の高さのヒルベルト という対比です。

二系統の使い分け

選択の軸は明快です。多角形や線分など面積を持つ形状を厳密に索引したい、逐次更新が多いなら R-Tree（実装としては R*-Tree）。点データが中心で、既に B+Tree やソートキーの基盤がある／専用索引を持ち込めないなら空間充填曲線が向きます。後者は分散環境とも相性が良く、Z-order やヒルベルトでキーを作れば、近い点が同じパーティションやページに集まり、データ局所性をそのまま得られます。次元数が数十以上に上がると両者とも次元の呪いで劣化し、そこからは別系統の 近似最近傍索引（HNSW/IVF-PQ） の領分になります。

まとめ