Evaluation of the Influence of Two-Level Clustering with BUB-Trees Indexing on the Optimization of Range Queries

摘要

A BUB-tree is an indexing structure based on B-trees and on a Z-order space filling curve, which transforms multidimensional data into a unique key, enabling the use of a mono-attribute index. We propose a two-level indexing structure relying on a partition of the data space into disjoint clusters. At the first level the clusters are indexed by a BUB-tree and at the second level the data of each cluster is itself indexed. Indexing the clusters provides an efficient query optimization because data filtering is performed at the cluster level, which reduces the data transferred from disk to memory. We compare the performance of our approach with single-level BUB-tree indexing on two types of queries: exact match queries and range queries, which play an important role in multidimensional databases, such as Data Warehouses or Geographic Information Systems. Our approach applies to any system supporting a partition of the attribute domains.