A Maintenance Algorithm for G~+-Tree Index Structures

摘要

We design a maintenance algorithm that attempts to optimize the spatial locality of G~+-trees by making the hyper-rectangle partitions as many as possible and the fractal partitions as few as possible. G~+-trees, derived from G-trees, are dynamic paged structures that offer more effective multi-dimensional point data access and better storage utilization compared to G-trees. However, after a long sequence of data insertions/deletions, the shape of partitions in a G~+-tree may go skewed or fractal. A skewed shape possibly causes some enclosed data relatively far away from each other; this may harm the spatial locality and data access performances. Therefore, a maintenance algorithm can enhance the spatial locality of G~+-trees.