A new indexing scheme supporting multi-attribute database applications: MAX

Abstract

Multi-attribute indexing schemes can be classified into seven classes according to the manner of partitioning multi-dimensional data space into regions, each of which contains all the records of a single data page, On the basis of this principle, we classify according to three properties of the hyperplane partitioning a region: the dimension of hyperplane, the number of hyperplanes, and the normal vector of hyperplane. Among the seven classes, we select a class as our indexing scheme model according to the complexity for maintaining hyperplane. From our model, we derive an indexing scheme, MAX, which handles multi-attribute data efficiently. In addition, a number of algorithms for manipulating multi-attribute data are given, together with their computational and I/O complexity. Moreover, we show that MAX is a kind of generalized B-tree, This means that MAX can be easily implemented on existing built-in B-trees in most storage managers in the sense that the structure of MAX is like that of B-tree. We measure the performance by testing against various realistic data and query sets, Results from the benchmark test indicate that MAX outperforms other indexing schemes on insertion, range query, and spatial join. For insertion, together with B-tree using z-transformation, MAX presents good performance in the aspects of CPU and I/O cost. Regardless of various clustering factors, the storage cost of MAX is remarkably low compared with KDB-tree and R-tree. We conclude that MAX is an efficient indexing scheme for multi-attribute database. IF MAX is fully implemented as an index method of storage manager, the performance of many applications using multi-attribute will be remarkably enhanced.