The RTree data structure can be considered a multidimensional version of BTree. Literally doezens of variants of the RTree 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 RTree [5] and CacheOblivious RTree [16]. Despite the variety of RTree 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 RTree structure and how queries are handled, anyone interested in RTrees handle insertions and deletions should consider the papers previously mentioned.
Consider a set S of objects in 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 RTree are rectangles in , 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 RTree contain records of the form (MBR, objectid) while internal nodes contain O(B) records of the form (MBR, childptr) where the MBR is the MBR of all records stored in the subtree rooted at the node pointed to by childptr
A set of rectangles and their corresponding RTree is depicted in figure 2.

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.