Some of the information here is derived from the University of California, Berkeley, The GiST Indexing Project web site and Marcel Kornacker's Thesis, Access Methods for Next-Generation Database Systems. The GiST implementation in PostgreSQL is primarily maintained by Teodor Sigaev and Oleg Bartunov, and there is more information on their website: GiST stands for Generalized Search Tree. It is a balanced, tree-structured access method, that acts as a base template in which to implement arbitrary indexing schemes. B+-trees, R-trees and many other indexing schemes can be implemented in GiST. One advantage of GiST is that it allows the development of custom data types with the appropriate access methods, by an expert in the domain of the data type, rather than a database expert. Traditionally, implementing a new access method meant a lot of difficult work. It was necessary to understand the inner workings of the database, such as the lock manager and Write-Ahead Log. The GiST interface has a high level of abstraction, requiring the access method implementor to only implement the semantics of the data type being accessed. The GiST layer itself takes care of concurrency, logging and searching the tree structure. This extensibility should not be confused with the extensibility of the other standard search trees in terms of the data they can handle. For example, PostgreSQL supports extensible B+-trees and R-trees. That means that you can use PostgreSQL to build a B+-tree or R-tree over any data type you want. But B+-trees only support range predicates (<, =, >), and R-trees only support n-d range queries (contains, contained, equals). So if you index, say, an image collection with a PostgreSQL B+-tree, you can only issue queries such as "is imagex equal to imagey", "is imagex less than imagey" and "is imagex greater than imagey"? Depending on how you define 'equals', 'less than' and 'greater than' in this context, this may be useful. However, by using a GiST based index, you could ask questions such as "find all images of horses" and "find all over-exposed images". All it takes to get a GiST access method up and running is to implement four user-defined methods, which define the behavior of keys in the tree. Of course these methods have to be pretty fancy to support fancy queries, but for all the standard queries (a la B+-trees, R-trees, etc.) they're relatively straightforward. In short, the GiST combines extensibility along with generality, code reuse, and a clean interface. There are seven methods required of the access method to use the GiST interface: consistent Given a predicate p on a tree page, and a user query, q, this method will return false if it is certain that both p and q cannot be true for a given data item. union This method consolidates information in the tree. Given a set of entries, this function generates a new predicate that is true for all the entries. compress Converts the data item into a format suitable for physical storage in the page. decompress The reverse of the compress method. Converts the page representation of the data item into a format that can be manipulated by the database. penalty Returns a value indicating the 'cost' of inserting the new entry into a particular branch of the tree. items will be inserted down the path of least penalty in the tree. picksplit When a page split is necessary, this function decides which entries on the page are to stay on the old page, and which are to move to the new page. same Returns true if two entries are identical, false otherwise. The current implementation of GiST withing PostgreSQL has two major limitations: GiST access is not concurrent and the GiST interface doesn't allow the development of certain data types, such as digital trees. (See papers by Aoki et. al) Solutions to the first of these problems appear in Marcel Kornacker's Thesis, however these ideas have not yet been put into practice in the PostgreSQL implementation. To see example implementations of index methods implemented using GiST, examine the following contrib modules: btree_gist B-Tree cube Indexing for multi-dimensional cubes intarray RD-Tree for one-dimensional array of int4 values ltree Indexing for tree-like stuctures rtree_gist R-Tree seg Storage and indexed access for 'float ranges' tsearch and tsearch2 Full text indexing