R-Trees

The R-Tree data structure can be considered a multidimensional version of B-Tree. Literally doezens of variants of the R-Tree have been developed since the original structure was proposed in [14] including the R+-Tree [17], the R*-Tree [8], and more recently the Priority R-Tree [5] and Cache-Oblivious R-Tree [16]. Despite the variety of R-Tree versions the basic tree structure and in particular the manner in which queries are performed is basically the same between versions. The description that follows will focus on the R-Tree structure and how queries are handled, anyone interested in R-Trees handle insertions and deletions should consider the papers previously mentioned.

R-Tree Structure

Consider a set S of objects in $\mathbb{R}^2$ on which we want to build an index structure. These could be polygons, lines, or sets of points. Rather than index the features themselves we can represent each feature by its minimum bounding rectangle or MBR. The index is then built on these MBRs. Thus we will consider that the objects stored in our R-Tree are rectangles in $\mathbb{R}^2$ , though in reality they can be more complex objects in any dimension (higher dimensional objects are represented by minimum bounding regions of the same dimension).

Leaf nodes in the R-Tree contain $O(B)$ records of the form (MBR, object-id) while internal nodes contain O(B) records of the form (MBR, child-ptr) where the MBR is the MBR of all records stored in the subtree rooted at the node pointed to by child-ptr

A set of rectangles and their corresponding R-Tree is depicted in figure 2.

Figure 2: Set of rectangles indexed by an R-Tree (top) and the corresponding R-Tree structure (bottom)

Queries

The query operation on R-Trees is very straightforward and operates as follows:

Proceedure Query( node v, query q )
1. if {v is a leaf}
   a. report all objects of v that intersect q
2. else {v is not a leaf}
   a. for {each child of v}
   	  (i) if {q intersects child.MBR}
   	  	  - call Query(child, q)

In the listing above query is a rectangular window query. The MBR of a subtree rooted at an interior node will generally cover an area greater than the union of all the leaf records of that subtree. Thus it is possible for a query to follow a path that results in no objects being reported.