R*-tree

R*-tree
Invented1990
Invented byNorbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, and Bernhard Seeger
Time complexity in big O notation
Operation Average Worst case
Search O(log n)
Insert O(log n)
Space complexity
Space O(n) O(n)

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.[1]

  1. ^ Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990). "The R*-tree: an efficient and robust access method for points and rectangles". Proceedings of the 1990 ACM SIGMOD international conference on Management of data - SIGMOD '90 (PDF). p. 322. doi:10.1145/93597.98741. ISBN 0897913655.