This article summarizes Antonin Guttman’s paper “R-Trees: A Dynamic Index Structure for Spatial Searching, SIGMOD 1984”. It names the motivation behind the R-tree and provides an overview of alternatives.

by Wanda Baltzer, bachelor student of the Hasso Plattner Institute, Potsdam

Motivation

Handling spatial data efficiently is an essential technique required by many applications dealing with multi-dimensional data, such as geo-data, multimedia, and spatio-temporal data. This problem has become more and more important as we try to handle more than the common two dimensions, e.g., when working with robotics and virtual reality [1]. Examples of applications that handle such data include computer-aided design, geographical information systems, radio frequency identification, and traffic control systems. All of these applications store large amounts of data, which makes efficient handling of search and update operations very important [2].

The R-tree [6] was proposed in 1984 by Antonin Guttman with the primary goal of handling geometrical data efficiently. It poses a substantial improvement to other data structures, which already tried to handle multi-dimensional point data. Some of these data structures are discussed in Guttman’s paper:

“Cell methods are not good for dynamic structures because the cell boundaries must be decided in advance. Quad trees and k-d trees do not take paging of secondary memory into account. K-D-B trees are designed for paged memory but are useful only for point data. The use of index intervals has been suggested […], but this method cannot be used in multiple dimensions.” [6]

While some of these examples provide better performance than the R-tree under certain circumstances, e.g., the quadtree when creating and updating indices [3], the R-tree has proven to be a good alternative, due to its outstanding overall performance and simple implementation [2].

The Data Structure

Guttman’s data structure represents data objects by intervals in several dimensions and works with a spatial database. This database consists of tuples, which represent spatial objects and have a unique identifier. The R-tree then refers to these identifiers in the index records. Leaf nodes contain index record entries with a tuple-identifier referring to a tuple in the database and an n-dimensional rectangle. Non-leaf nodes contain entries with a child-pointer as the address of a lower node in the tree and an n-dimensional rectangle covering all rectangles in the lower node’s entries.

This n-dimensional rectangle is assembled by n closed-bound intervals. So if you have a two-dimensional rectangle with the two intervals [2, 5], [1, 4], you receive a rectangle that looks like this:

Each R-tree has a maximum number of entries in a node. This number is referred to as M. Depending on the maximum number of entries, the minimum number is calculated with m = M/2. This property is used to decide whether the tree has to be reorganized. Another property of the R-tree is that the rectangle in the index records has to be the smallest rectangle possible while containing all corresponding tuples or rectangles.

To summarize the above, the R-tree consists of leaf node entries containing identifiers referring to the data tuples in the database, and of non-leaf node entries, which point to an address of a child node. A leaf node entry includes a rectangle, which encloses the data object, whereas a non-leaf node entry includes a rectangle that encloses all entries of the child node it points to. This structure is illustrated in Figure 2.

Searching and Updating Algorithms Guttman’s paper gives algorithms for searching and updating the index structure. The following presents an overview of how the data structure works.

Firstly, the search algorithm. When searching for all index records whose rectangles overlap a search rectangle, the algorithm checks each entry of the considered node for whether the rectangle overlaps the search rectangle. If so, the search algorithm again checks the corresponding child node for an overlap. This continues until the considered node is a leaf. If the algorithm then finds a rectangle that overlaps the search rectangle, this entry is returned as a qualifying record.

There are other search algorithms, which might be useful in some applications. Using the described search algorithm, these operations are easy to implement. An example of another search algorithm is FindLeaf, which searches for a certain entry in the tree.

However, there is a disadvantage of the algorithm:

“[…] more than one subtree under a node visited may need to be searched, hence it is not possible to guarantee good worst-case performance. Nevertheless with most kinds of data the update algorithms will maintain the tree in a form that allows the search algorithm to eliminate irrelevant regions of the indexed space, and examine only data near the search area.” [6]

One of these update algorithms is CondenseTree. It is invoked in the deletion algorithm after an entry has been deleted from a leaf node. It then checks whether this leaf node contains too few entries. If it has less than m entries, the node and the pointer in the parent node are eliminated. The eliminated node is stored temporarily in an array, Q. The algorithm then adjusts all covering rectangles, checks the number of entries of the parent node, and, if necessary, repeats all steps. Finally, the entries of the nodes stored in Q are reinserted into the tree.

There is a similar update operation in the B-tree, where two or more adjacent nodes are merged. Such an approach could have been possible. Nevertheless, Guttman chose a different one.

“We chose re-insertion instead for two reasons: first, it accomplishes the same thing and is easier to implement because the Insert routine can be used. Efficiency should be comparable because pages needed during re-insertion usually will be the same ones visited during the preceding search and will already be in memory. The second reason is that reinsertion incrementally refines the spatial structure of the tree, and prevents gradual deterioration that might occur if each entry were located permanently under the same parent node.” [6]

AdjustTree is another updating algorithm, which is required in the insertion algorithm to adjust the covering rectangles and propagate necessary node splits. Node splits are needed when a new entry is added to a node already containing M entries. The M+1 entries are then divided between two nodes. Here it must be prevented that both nodes need to be examined during subsequent searches. The decision on which node to visit is based on whether the covering rectangle overlaps the search rectangle. That is why the area of the two created rectangles after the split has to be minimized, as shown in Figure 3.