The R-tree access method organizes data in a tree-shaped structure
called an R-tree index. The index uses a bounding
box, which is a rectilinear shape that completely contains
the bounded object or objects. Bounding boxes can enclose data objects
or other bounding boxes.
Bounding boxes are usually stored as a set of coordinates of equal
dimension as the bounded object. While it is useful for performance
reasons to choose the bounding box that is as small as possible, the
R-tree access method does not require it. The minimum bounding box
is often, however, the most efficient one. For example, the minimum
bounding box for a two-dimensional circle is a square whose side is
equal to the diameter of the circle. The minimum bounding box for
a three-dimensional sphere is a cube whose edge is equal to the diameter
of the sphere.
Tip: A dimension of a bounding box can
be time or some other nonspatial quantity.
The lower part of the following figure shows a set of bounding
boxes that enclose data objects and other bounding boxes. In the diagram,
the data objects are shaded.
Important: Data objects are
only shown for bounding boxes R8, R9, and R10. The other bounding
boxes at the leaf level (R11 through R19) also contain data items,
but they are omitted from the figure to simplify the graphic.
Figure 1: R-tree index structure
As the figure shows, bounding boxes can enclose a single data object
or one or more bounding boxes. For example, bounding box R8, which
is at the leaf level of the tree, contains the data object D1. Bounding
box R3, which is at the branch level of the tree, contains the bounding
boxes R8, R9, and R10. Bounding box R1, which is at the root level,
contains the bounding boxes R3, R4, and R5.
The R-tree access method evaluates the index entries (data objects
and bounding boxes) as opaque objects (strings of bytes). The R-tree
access method uses the support and strategy functions to interpret
these objects.
