G-tree is a data structure designed to provide multidimensional access in databases. It has the self-balancing property of B+-tree. In this paper, performance evaluation of G-tree is provided for various data distributions. For point queries, the experiments show that its retrieval and update performance is similar to that of B+-trees independently of the data distribution. For range queries, the performance varies significantly with the data distributions. While the performance is good for the 2-dimensional case, it deteriorates as the number of dimensions increases. This empirical evidence is confirmed by an analytical proof, which also yields a simple way of computing the expected number of data pages accessed. This analytical result which shows that the number of data pages accessed by a range query increases exponentially with the number of dimensions applies to many multi-dimensional schemes. We also apply the G-tree to fuzzy database and show empirically that it has good performance for imprecise queries on relatively imprecise data. But it is less efficient for precise queries on relatively precise data.
