Generalized Search Trees for Database Systems (Extended Abstract).pdf

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@cs.berkeley.edu naughton@cs.wisc.edu avi@cs.berkeley.edu developing domain-specific search trees is problematic. Abstract The effort required to implement and maintain such data structures is high. As new applications need to be sup- This paperintroducesthe GeneralizedSearchTree (GiST), anindex ported, new tree structures have to be developed from structuresupportinganextensiblesetof queriesanddatatypes. The scratch, requiring new implementations of the usual tree GiST allows new data types to be indexed in a mannersupporting facilities for search, maintenance, concurrency control queries natural to the types; this is in contrastto previouswork on and recovery. treeextensibility which only supportedthe traditional setof equality and rangepredicates. In a single data structure,the GiST provides 2. Search Trees For Extensible Data Types: As an alter- all the basicsearchtree logic requiredby a databasesystem,thereby native to developing new da