要旨

コンピューティングにおいて、GiSTまたは Generalized Search Tree は、さまざまなディスクベースの検索ツリーを構築するために使用できるデータ構造とAPIです。GiST はB+ ツリーを一般化したものであって、格納されるデータのタイプやサービスされるクエリについて何も想定せずに、並列かつ回復可能な高さバランス検索ツリー インフラストラクチャを提供します。GiST を使用すると、B+ ツリー、R ツリー、hB ツリー、RD ツリーなど、さまざまなよく知られたインデックスを簡単に実装できます。また、新しいデータ タイプ専用のインデックスを簡単に開発することもできます。GiST は、4 倍木やプレフィックス木(トライ)などの高さバランスの取れていないツリーの実装には直接使用できませんが、プレフィックス木と同様に、非可逆圧縮などの圧縮をサポートしています。GiST は、スーパーセットの階層に自然に順序付けできる任意のデータ タイプに使用できます。データ タイプのサポートとツリー レイアウトの点で拡張可能であるだけでなく、拡張機能の作成者は任意のクエリ述語をサポートできます。

GiST は、データベース システムのコンテキストにおけるソフトウェア拡張性の一例です。これにより、データベース システムを簡単に進化させて、新しいツリー ベースのインデックスをサポートできます。これは、さまざまなインデックス設計のアプリケーション固有の側面を捕捉するのに十分な狭いAPIからコア システム インフラストラクチャを分離することによって実現されます。GiST インフラストラクチャ コードは、ディスク上のインデックス ページのレイアウト、インデックスの検索とインデックスからの削除のアルゴリズム、および高い同時実行性のためのページ レベルのロックやクラッシュ回復のための先行書き込みログなどの複雑なトランザクションの詳細を管理します。これにより、新しいツリー ベースのインデックスの作成者は、データベース システムの内部に精通することなく、新しいインデックス タイプの新しい機能 (たとえば、検索用にデータのサブセットを記述する方法) の実装に集中できます。

GiST はもともとブール選択クエリに答えるために設計されましたが、最近傍検索や大規模なデータセットに対する さまざまな形式の統計的近似もサポートできます。

最も広く使用されている GiST 実装は、PostgreSQL リレーショナル データベースにあります。また、 Informix Universal Server やスタンドアロン ライブラリ libgist に も実装されています。

PostgreSQL GiST 実装には、可変長キー、複合キー、同時実行制御、リカバリのサポートが含まれています。これらの機能は、すべての GiST 拡張機能に継承されています。GiST を使用して開発され、PostgreSQL とともに配布されている寄稿モジュールがいくつかあります。例:

• rtree_gist、btree_gist - R ツリーと B ツリーの GiST 実装
• intarray - int4 の 1 次元配列のインデックス サポート
• tsearch2 - インデックスアクセスによる検索可能な（全文）データタイプ
• ltree - ツリー構造として編成されたデータに対するデータ型、インデックスアクセス方法、クエリ
• hstore - (キー、値) データのストレージ
• キューブ - 多次元キューブを表すデータ型

PostgreSQL GiST 実装は、PostGIS (地理情報システム) および BioPostgresバイオインフォマティクスシステムのインデックス作成サポートを提供します。

• Joseph M. Hellerstein、Jeffrey F. Naughton、Avi Pfeffer。「データベース システムのための一般化された検索ツリー」。第 21 回国際大規模データベース会議議事録、チューリッヒ、1995 年 9 月、562–573 ページ。
• Marcel Kornacker、C. Mohan、Joseph M. Hellerstein。「一般化検索ツリーにおける並行性と回復」。Proc. ACM SIGMOD Conf. on Management of Data、アリゾナ州ツーソン、1997 年 5 月、62 ～ 72 ページ。
• Paul M. Aoki。「一般化検索ツリーにおける「検索」の一般化」。Proc. 14th Int'l Conf. on Data Engineering、フロリダ州オーランド、1998 年 2 月、380–389 ページ。
• Marcel Kornacker. 高性能一般化検索ツリー、第 24 回国際大規模データベース会議議事録、スコットランド、エジンバラ、1999 年 9 月。
• Paul M. Aoki. 「すべての価値を認識し、何もコストを認識しないデータブレードの構築を回避する方法」、科学および統計データベース管理に関する第 11 回国際会議議事録、オハイオ州クリーブランド、1999 年 7 月、122 ～ 133 ページ。

• GiST 研究プロジェクト ウェブサイト
• PostgreSQL GiST 開発
• PostgreSQL の GiST サポートに関するドキュメント
• GiST を使用した PostgreSQL 拡張機能の開発(ロシア語)
• PostgreSQL の GiST wiki
• ポストGIS
• バイオポストグレス