Multiattribute indexing with m-Q-trees

A wide class of multidimensional indexes employs a recursive partitioning of the data space as the kd-tree does. In this paper we present the m-Q-tree as a multidimensional data structure that can achieve the maximum degree of 2/sup m/ children in every node (where m is the number of index attributes) and a maximum of only one underflow page per node. We describe the m-Q-tree, and give searching and inserting algorithms. In order to develop a solution for building the m-Q-tree we define and use a conceptual tool, called prefix graph, which permits us to manage the regions associated to all sons of every node. The proposed algorithm is of order O(m). Finally, we present the results of a series of tests which indicate that the structure preforms well. m-Q-tree gives a general technique for declustering data in a parallel database. We propose m-Q-tree as a new general access method which permits the exploitation of the potential parallelism of all relational operations, in addition to favour the execution of complex queries, including different kinds of conditions over several attributes fro one or more relations.