Generalizing “search” in generalized search trees

The generalized search tree, or GiST, defines a framework of basic interfaces required to construct a hierarchical access method for database systems. As originally specified, GiST only supports record selection. We show how a small number of additional interfaces enable GiST to support a much larger class of operations. Members of this class, which includes, nearest-neighbor and ranked search, user-defined aggregation and index-assisted selectivity estimation, are increasingly common in new database applications. The advantages of implementing these operations in the GiST framework include reduction of user development effort and the ability to use industrial strength concurrency and recovery mechanisms provided by expert implementers