R* Ағаштары: Кеңістіктік Ақпаратты Индекстеудің Бір Түрі

A variant of R trees used for indexing spatial information

In data processing R* trees are a variant of R trees used for indexing spatial information. R* trees have slightly higher construction cost than standard R trees, as the data may need to be reinserted; but the resulting tree will usually have a better query performance. Like the standard R tree, it can store both point and spatial data. It was proposed by Norbert Beckmann, Hans Peter Kriegel, Ralf Schneider, and Bernhard Seeger in 1990.

Improved split heuristic produces pages that are more rectangular and thus better for many applications. Reinsertion method optimizes the existing tree but increases complexity. Efficiently supports point and spatial data at the same time.

The R* tree uses the same algorithm as the regular R tree for query and delete operations. When inserting, the R* tree uses a combined strategy. For leaf nodes, overlap is minimized, while for inner nodes, enlargement and area are minimized. When splitting, the R* tree uses a topological split that chooses a split axis based on perimeter, then minimizes overlap. In addition to an improved split strategy, the R* tree also tries to avoid splits by reinserting objects and subtrees into the tree, inspired by the concept of balancing a B tree. Worst case query and delete complexity are thus identical to the R Tree. The insertion strategy to the R* tree is with more complex than the linear split strategy of the R tree, but less complex than the quadratic split strategy for a page size of objects and has little impact on the total complexity. The total insert complexity is still comparable to the R tree: reinsertions affect at most one branch of the tree and thus reinsertions, comparable to performing a split on a regular R tree. So, on overall, the complexity of the R* tree is the same as that of a regular R tree. An implementation of the full algorithm must address many corner cases and tie situations not discussed here.