GiST・SP-GiST 汎用インデックスフレームワークの内部

GiST が抽象化したもの

B+Tree も R-Tree も、構造を抽象化すると驚くほど似ています。どちらも平衡木で、内部ノードは「子の配下に何があるか」を要約したキーを持ち、探索は問合せと無関係な枝を刈りながらルートから降ります。違うのは キーの意味と、枝刈りの判定条件 だけです。B+Tree のキーは「区間の境界」で、R-Tree のキーは「子を覆う最小外接矩形（MBR）」です。

GiST（Generalized Search Tree、汎用探索木） は、この共通部分 ——平衡木の構造・ページ分割・WAL・並行制御・探索の枝刈り—— をフレームワーク側に固定し、キーの意味と判定条件だけを型側に委ねる という発想です。新しい索引を作りたい型の作者は、木のアルゴリズムを一から書く必要がなく、後述する 少数の演算子（メソッド） を実装するだけで済みます。R-Tree（幾何）、範囲型の索引、pg_trgm による全文・類似検索、intarray など、見た目の異なる索引がすべて同じ GiST の上に乗っているのは、このためです。

拡張の核：型が実装する演算子

GiST の型側が実装するメソッドは、役割によって 正しさを担うもの と 品質を担うもの に分かれます。この区別が GiST 理解の要です。

挿入はこう進みます。ルートから各レベルで、子キーごとに penalty（その子に新エントリを入れたときのコスト増、R-Tree なら MBR の面積増）を計算し、最小ペナルティの子へ降ります。葉が満杯なら picksplit で2つに割り、分割で生じた各グループのキーを union で合成して親へ伝播させます。penalty と picksplit の出来が、後の探索で辿る枝の数を左右します。

consistent：キー一貫性という正しさの保証

GiST の正しさを一手に背負うのが consistent（キー一貫性） メソッドです。これは内部ノードのキー p と問合せ述語 q を受け取り、「このキー p が覆う配下に、q を満たす要素が 存在しうるか」を真偽で返します。探索は次の不変条件のもとで枝刈りします。

GiST 探索 search(node, q):
  for each entry e in node:
      if consistent(key(e), q) が偽:  この枝を刈る   # 配下に答えは無いと確定
      else:
          if node が葉:  e を結果候補へ
          else:          search(child(e), q)        # 一致しうる枝だけ降りる

ここで決定的に重要なのは、consistent が満たすべき 片側の保証 です。

• consistent が 偽 を返したら、その配下に答えは 一つも無い（false negative を絶対に出してはならない）。
• consistent が 真 を返しても、配下に答えがあるとは限らない（false positive は許される）。

つまり consistent は「枝刈りしてよいか」を 安全側に 判定します。偽陽性（無駄に降りる枝）は性能を落とすだけですが、偽陰性（本来降りるべき枝を刈る）は結果の欠落というバグ になります。R-Tree なら「問合せ矩形が子 MBR と重ならないなら偽」と書けばこの保証を満たします。範囲型なら「親が覆う区間と問合せ区間が交差しないなら偽」です。新しい型の索引を作る難しさの大半は、この 片側保証を満たす consistent を正しく書けるか に集約されます。

penalty と picksplit：木の品質を決める

正しさが consistent／union で担保される一方、探索が速いか遅いか は penalty と picksplit が決めます。GiST は R-Tree と同じく キーの重なりを許す 平衡木なので、親キー同士が大きく重なると、一回の探索で複数の枝が consistent=真となり、枝刈りが効かなくなります。R-Tree の分割戦略 でいう「子 MBR の重なり最小化」と同じ問題です。

• penalty は挿入先の選択を左右します。R-Tree 系なら「新エントリを入れたときの MBR の面積増」をコストとして返し、フレームワークは最小ペナルティの子へ降ろします。面積増が小さい子を選ぶほど、親キーが無駄に膨らまず重なりが抑えられます。
• picksplit は満杯ノードの2分割を決めます。同じエントリ集合でも、分け方次第で2つの親キーの重なり・総面積が大きく変わります。良い picksplit は「2グループの union がなるべく重ならず、なるべく小さくなる」分割を選びます。

これらは結果の正しさには影響しません。雑な penalty／picksplit でも答えは正しく返りますが、重なりが増えて探索が全枝走査へ劣化します。正しさは consistent／union、速さは penalty／picksplit という分業が、GiST の設計をきれいに保っています。

一つの木に多様な索引が乗る理由

同じ GiST の骨格に、メソッドの中身を差し替えるだけで異なる索引が生まれます。これが「汎用」たるゆえんです。

全文や trigram で使われるのが 署名（signature） という近似要約です。配下に現れる語や trigram の集合を、固定長のビットベクタへハッシュで畳み込みます。union は子署名の OR、consistent は「問合せ語のビットが署名に立っているか」で判定します。署名は偽陽性を持つ（別の語が同じビットを立てうる）ぶん枝刈りは甘くなりますが、consistent の片側保証（偽なら本当に無い）は崩れないので 正しさは保たれます。これは GIN の転置構造 が要素キーを正確に持つのと対照的で、GiST は近似要約で平衡木に押し込むぶん索引が小さく更新も軽い、という性格になります。

SP-GiST：空間分割を抽象化するもう一つの枠組み

GiST が「重なりを許す平衡木」を抽象化するのに対し、SP-GiST（Space-Partitioned GiST） は 空間を互いに素な領域へ再帰分割する 木を抽象化します。quadtree（四分木）、kd-tree、radix trie（基数木）がその代表で、いずれも一つの領域を重ならない部分領域へ割っていく構造です。

SP-GiST の型側は GiST とは別のメソッド群を実装します。中心は config（節点の分割方式の宣言）、choose（挿入する子を選ぶ）、picksplit（葉を内部節点へ昇格させる分割）、inner_consistent / leaf_consistent（内部・葉での枝刈り判定） です。ここでも consistent が枝刈りの正しさを担うのは GiST と同じで、「この部分領域に問合せが交差しないなら降りない」という片側保証を満たします。

重なりが無いぶん、SP-GiST は どの問合せ点も必ず一本の枝に属する ため、点の等値・近傍探索で枝刈りが鋭く効きます。text に対する radix trie は文字を辿るだけで共通接頭辞を共有でき、prefix 検索（LIKE 'abc%'）に強いのが典型です。代償は非平衡性で、データが偏ると木が深く伸びます。

GIN との位置づけ

同じ「含む」系を扱える GIN（汎用転置索引） と GiST は、しばしば対比されます。GIN は要素キーごとに行 TID の正確な posting list を持つ転置索引で、全文・配列・JSONB の包含検索で速い反面、1行が多数のキーを生むため更新が重くなります。GiST は近似要約（MBR・署名）を平衡木に束ねるため、索引が小さく更新が軽い 代わりに、署名の偽陽性で検索が GIN より遅くなりがちです。おおむね 検索主体で更新が少ないなら GIN、更新が多い／幾何・範囲を扱うなら GiST、という 前述の使い分け がそのまま当てはまります。

まとめ