汎用検索ツリー
汎用検索ツリー (GiST: Generalized Search Tree) はディスク上に木構造の検索機能を実現する データ構造 と API である。 GiSTはB+木を一般化したもので、並列実行性能が高くリカバリが可能な高さがバランスされた検索木のフレームワークを提供する。 また、保存できるデータ型や検索クエリに制限が無い。
GiSTは良く利用されるインデックス(B+木, R木, hB木, RD木 など)の実装に利用できる。 また、新しいデータ型に対して特化したインデックスを開発することも容易である。 ただし、GiST を使っても直接的には高さバランスではないツリー構造 (八分木やトライ木) を実装することはできない。 また、GiST は可逆および非可逆の圧縮をサポートしているが、各ノードのデータ型は同一でなければならない。 リーフにはノードとは異なる型を用いることもできる。
データ型と木の配置だけではなく、クエリの検索条件(演算子)も拡張することができる。
最も広く利用されているGiSTは、PostgreSQL 関係データベースにおける実装である。 また、Informix Universal Server でも外部ライブラリ libgist によってGiSTが利用できる。
データベースの観点では、GiSTはソフトウェアの拡張性の一例である。 データベースに対して新しい木構造のインデックスを追加することが容易になる。 アプリケーションごとの様々なインデックスの設計に対応できるよう、コアシステムから数個の API が外部に公開されている。