The R+ -Tree: A Dynamic Index for Multi-Dimensional Objects.

The problem of indexing multidimensional objects is considered. First, a classification of existing methods in given along with a discussion of the major issues involved in multidimensional data indexing. Second, a variation to Guttman's R-trees (R+ -trees) that avoids overlapping rectangles in intermediate nodes of the tree is introduced. Algorithms for searching, updating, initial packing and reorganization of the structure are discussed in detail. Finally, we provide analytical results indicating that R+ -tree achieve up to 50% savings in disk accesses compared to an R-tree when searching files of thousands of rectangles