We propose a new R-tree structure that outperforms all the older ones. The heart of the idea is to impose a linear ordering on the data rectangles. This ordering has to be 'good', in the sense that it should cluster 'similar' data rectangles together, to minimize the area and perimeter of the resulting minimum bounding rectangles (MBRs). Among the orderings we tried, the '2D-c' method, the one that uses the (2d) hilbert value of the center of the rectangles, gives the best results.

For a static database, the proposed ordering achieves superior packing, outperforming older packing methods [25], and the best dynamic method (R*-trees [3]). The savings are as high as 36% on real data.

more importantly, we introduce a dynamic variation, the Hilbert R- tree: : Given the ordering, every node has a well- defined set of sibling nodes; thus, we can deploy the deferred splitting algorithms of the B* -trees. By adjusting the split policy, the Hilbert R-tree can achieve as high utilization as desired. We show that a '3-to-4' split policy achieves good results, consistently outperforming the R* -trees, with up to 28% savings on real data.