GiST

From Wikipedia, the free encyclopedia

In computing, GiST or Generalized Search Tree, is a data structure and API which can be used to build almost any kind of search tree on almost any kind of data. With GiST it is possible to build B+ trees, kd-trees, hB-trees, RD-trees, R-trees and many others. However, it can not be used to represent a prefix tree (trie), although it can support other forms of compression, including lossy compression. GiST can be used efficiently for any data type which can be naturally ordered into a hierarchy of supersets. Not only is it extensible in terms of data type support and tree layout, it allows custom defined query types. GiST is implemented in the PostgreSQL relational database and has also been implemented as a library, libgist.

GiST is useful because it allows new tree-based indexes to be created easily. In PostgreSQL, the GiST infrastructure code manages the layout of the index pages themselves, the algorithms for searching indexes and deleting from indexes, and other complex implementation details, such as page-level locking for high concurrency and write-ahead logging for crash recovery. This allows authors of new tree-based indexes to focus on implementing the novel features of the new index type.

[edit] References

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, Zürich, September 1995, 562-573.