Generalized Search Trees for Database Systems

TLDR

The paper proposes the Generalized Search Tree (GiST), a flexible index structure that supports a wide range of queries and data types. GiST unifies traditional tree structures by providing a single code base that can be configured to act as B+-trees, R-trees, or RD-trees through simple method implementations, enabling extensible indexing for new data types. A preliminary performance evaluation of the RD-tree variant shows promising results and highlights how tree indices behave across different datasets.

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.