tailieunhanh - Generalized Search Trees for Database Systems

“We’re going to have to look at schools,” the president said, later adding that Sandy Hook “ should be a wake-up call for all of us to say that if we are not getting right the need to keep our children safe, then nothing else matters.” Nothing else matters. The NRA agreed about making our schools safer for our children. A few days after the president’s press conference, we announced the NRA School Shield safety program to put trained, qualified, armed police or security officers in every single school in the country. . | Generalized Search Trees for Database Systems Extended Abstract Joseph M. Hellerstein Jeffrey F. Naughton Avi Pfeffer University of Wisconsin Madison University of Wisconsin Madison University of California Berkeley jmh@ naughton@ avi@ 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. 1 Introduction An efficient implementation of search trees is crucial for any database system. In traditional relational systems B -trees Com79 were sufficient for the sorts of queries posed on the usual set of alphanumeric data types. Today database systems are increasingly being deployed to support new applications such as geographic information systems multimedia systems CAD tools document libraries sequence databases fingerprint identification systems biochemical databases etc. To support the growing set of applications search trees must be extended for maximum flexibility. This requirement has motivated two major research approaches in extending search tree technology 1. Specialized Search Trees A large variety