R-Trees

R-trees are a N-dimensional extension of B+-trees, but are used for spatial access methods i.e., for indexing multi-dimensional information; for example, the (X, Y) coordinates of geographical data. Represent a spatial object by its minimum bounding rectangle (MBR). Supported in many modern database systems, along with variants like R+ -trees and R*-trees. The data structure splits space with hierarchically nested, and possibly overlapping boxes. The data for this section is taken from paper by Antonm Guttman [6]

A rectangular bounding box is associated with each tree node.

• Bounding box of a leaf node is a minimum sized rectangle that contains all the rectangles/polygons associated with the leaf node.
• The bounding box associated with a non-leaf node contains the bounding box associated with all its children.
• Bounding box of a node serves as its key in its parent node (if any)
• Bounding boxes of children of a node are allowed to overlap.

Figure 2.7: Sample R-tree

rtree.png