Design And Implementation Of Generalized R Tree

Object-relational database management system(ORDBMS) is a mature product which on the basis of combination of the object-oriented mangement system and database technology.It supports complex queries to complex data,so it can do better when doing query to multi-media, Web application,as well as some new areas of business applications.ORDMS provides convenient functionality to users to allow them defining new data type(called user-defined datatype,UDT) and support functions.The extension of data type will inevitably require an extensible indexing mechanism to support UDTs.Due to current datas have some feature that different from traditional data types,like highly dimensions,complex structures and larege quantity.So,traditional indexing method can not meet the need of users' queries.For some particular UDTs,traditional indexes even can not handle.Obviously,the limitations of these indexes affect the efficiency of database system.As a result,to develop a highly efficient index which could retrieve any type of keyword is a certain requirement of ORDBMS.This paper proposes a new method called GRT(Generalized R-tree) which can be used in relational and multi-dimensional database management system.This method mainly solves the problem that the traditional R tree can only index datas with coordinate type.It achieves the extensibility of indexed key types.Except common tree functions, GRT leaves users a set of key methods,which defined by users according to the requirement of some physical system.The advantage of this index is that:it could be used to index the abstract data types which defined by users,making retrieve processing more flexible and more extensible.The author's main works are listed as follows:(1) Analyze the advantage and limitation of traditional R-tree structure.In accordance with R-tree's defect that it doesn't support UDT,and combined the extensibility of GIST,we design a new generalized R-tree indexing mechinism—GRT.This method is used to retrieve user-defined data types.(2) From two sides to illustrate the generality of GRT method:the structure character and the process of tree algorithms.They prove that the GRT can achieve the generality of data type and the dimension of indexed keys efficiently.We also provide examples to show the extensibility of GRT.(3) According to the features of PostgreSQL database,we design and develop GRT on this extensible platform.Combined with the experimental results,we prove that GRT method has highly extensibility and efficiency.