汎用検索ツリー

汎用検索ツリー（GiST）とは

汎用検索ツリー（GiST: Generalized Search Tree）は、ディスク上に木構造の検索機能を実装するためのデータ構造とAPIです。これは、B+木を一般化したもので、並列実行性能が高く、リカバリが可能なバランスの取れた検索木のフレームワークを提供します。

GiSTの主な特徴

汎用性: 保存できるデータ型や検索クエリに制限がなく、様々な種類のデータに対応したインデックスを作成できます。
拡張性: B+木、R木、hB木、RD木などの既存のインデックス構造を実装できるだけでなく、新しいデータ型に特化したインデックスも容易に開発できます。
柔軟性: データ型、木の配置だけでなく、検索条件（演算子）も拡張可能です。
高度な並列処理: 並列実行性能が高く、大量のデータを効率的に処理できます。
リカバリ: クラッシュ時にもデータの整合性を保つリカバリ機能を備えています。

GiSTの構造と動作

GiSTのフレームワークは、ディスク上のインデックスページのレイアウトを管理します。検索、削除、ページ単位ロック、高い並列実行性能、クラッシュリカバリのためのログ先行書き込み（WAL）などの機能が提供されます。これにより、開発者はデータベースシステムの内部構造を深く理解していなくても、データの特徴量抽出などのアプリケーション固有のロジックに注力できます。

ただし、GiSTを使用しても、高さバランスではないツリー構造（八分木やトライ木など）を直接実装することはできません。また、可逆および非可逆の圧縮をサポートしていますが、各ノードのデータ型は同一である必要があります（リーフノードは異なる型を使用できます）。

GiSTの応用

GiSTは当初、厳密な検索を目的として設計されましたが、近傍検索もできるよう拡張されました。さらに、巨大なデータセットから多様な形式で統計情報を取得することも可能です。

最も広く利用されているのは、PostgreSQL関係データベースにおける実装です。また、Informix Universal Serverでも外部ライブラリlibgistによってGiSTが利用できます。

データベースの観点から見ると、GiSTはソフトウェアの拡張性の好例であり、新しい木構造インデックスを容易に追加できる基盤を提供します。

PostgreSQLにおけるGiST

PostgreSQLのGiSTの実装は、可変長キー、複合キー、並行性制御、リカバリをサポートしており、これらの機能はGiSTをベースとするインデックスにも継承されます。PostgreSQLには、GiSTを利用して開発された多くの貢献モジュールが提供されています。

rtree_gist, btree_gist: R木やB木をGiSTで再実装したもの。
intarray: 1次元のint4の配列に対するインデックス。
tsearch2: 全文検索インデックス。
ltree: 木に似た構造を内包するデータ型の検索。
hstore: キーと値の組を保存するデータ型。
cube: 多次元の立方体。

PostgreSQLのGiSTの実装は、PostGIS（地理空間情報システム）やBioPostgres（バイオインフォマティクス）など、様々な分野で活用されています。

まとめ

GiSTは、汎用性と拡張性の高いインデックスフレームワークであり、多様なデータや検索要件に対応できます。PostgreSQLをはじめとするデータベースシステムでの利用は、その柔軟性と強力な機能を示しており、新しいデータ型や検索方法に対応したインデックス開発を促進します。

参考文献

Joseph M. Hellerstein, Jeffrey F. Naughton and Avi Pfeffer. Generalized Search Trees for Database Systems. Proc. 21st Int'l Conf. on Very Large Data Bases, Zurich, September 1995, 562-573.
Marcel Kornacker, C. Mohan and Joseph M. Hellerstein. Concurrency and Recovery in Generalized Search Trees. Proc. ACM SIGMOD Conf. on Management of Data, Tucson, AZ, May 1997, 62-72.
Paul M. Aoki. Generalizing "Search" in Generalized Search Trees. Proc. 14th Int'l Conf. on Data Engineering, Orlando, FL, Feb. 1998, 380-389.
Marcel Kornacker. High-Performance Generalized Search Trees, Proc. 24th Int'l Conf. on Very Large Data Bases, Edinburgh, Scotland, September 1999.
Paul M. Aoki. How to Avoid Building DataBlades That Know the Value of Everything and the Cost of Nothing, Proc. 11th Int'l Conf. on Scientific and Statistical Database Management, Cleveland, OH, July 1999, 122-133.

外部リンク

GiST research project website
PostgreSQL GiST Development
GiSTインデックス (PostgreSQL文書)
Developing PostgreSQL extension with GiST （ロシア語）
GiST in PostgreSQL wiki
PostGIS
* BioPostgres

もう一度検索