Abstract.
This paper introduces the Generalized Search Tree (GiST), an
index structure supporting an extensible set of queries and data
types. The GiST allows new data types to be indexed in a manner
supporting queries natural to the types; this is in contrast to
previous work on tree extensibility which only supported the
traditional set of equality and range predicates. In a single data
structure, the GiST provides all the basic search tree logic required
by a database system, thereby unifying disparate structures such as
B+-trees and R-trees in a single piece of code, and opening the
application of search trees to general extensibility.
To illustrate the flexibility of the GiST, we provide simple
method implementations that allow it to behave like a B+-tree, an
R-tree, and an RD-tree, a new index for data with set-valued
attributes. We also present a preliminary performance analysis of
RD-trees, which leads to discussion on the nature of tree indices and
how they behave for various datasets.
Last modified: Fri May 5 12:34:10 1995 by Joe Hellerstein
jmh@cs.berkeley.edu