R-Trees R-trees are a N-dimensional extension of B+-trees,useful for indexing sets of rectangles and other polygons Supported in many modern database systems,along with variants like R+- trees and R*-trees. Basic idea:generalize the notion of a one-dimensional interval associated with each B+-tree node to an N-dimensional interval,that is,an N-dimensional rectangle. Will consider only the two-dimensional case(N=2) generalization for N>2 is straightforward,although R-trees work well only for relatively small N A polygon is stored only in one node,and the bounding box of the node must contain the polygon The storage efficiency or R-trees is better than that of k-d trees or quadtrees since a polygon is stored only once Database System Concepts-7th Edition 24.21 ©Silberscha乜，Korth and SudarshanDatabase System Concepts - 7 24.21 ©Silberschatz, Korth and Sudarshan th Edition R-Trees ▪ R-trees are a N-dimensional extension of B+ -trees, useful for indexing sets of rectangles and other polygons. ▪ Supported in many modern database systems, along with variants like R+ - trees and R*-trees. ▪ Basic idea: generalize the notion of a one-dimensional interval associated with each B+ -tree node to an N-dimensional interval, that is, an N-dimensional rectangle. ▪ Will consider only the two-dimensional case (N = 2) • generalization for N > 2 is straightforward, although R-trees work well only for relatively small N ▪ A polygon is stored only in one node, and the bounding box of the node must contain the polygon • The storage efficiency or R-trees is better than that of k-d trees or quadtrees since a polygon is stored only once