The R-Tree Secondary Access Method

Home | Previous Page | Next Page R-Tree Secondary Access Method Concepts >

The R-Tree Secondary Access Method

R-tree is a type of secondary access method that is specifically designed to index table columns that contain the following types of data:

Multidimensional data, such as:
- Spatial data in two or three dimensions
  An extra dimension that represents time could also be included.
- Combinations of numerical values treated as multidimensional values, such as a configuration for a house that includes the number of stories, the number of bedrooms, the number of baths, the age of the house, and the square feet of floor space
Range values, as opposed to single point values, such as the time of a television program (9:00 P.M. to 9:30 P.M.) or the north-south extent of a county on a map

Important:

You can build R-tree indexes only on a single column of a table or on the result of a single function (functional R-tree indexes); you cannot build a single R-tree index on multiple columns.

To index multiple attributes, incorporate them into a single data type. For more information on how to create a new data type, refer to Designing a User-Defined Data Type.

The R-tree access method is implemented internally using the Virtual-Index Interface, a mechanism provided with Dynamic Server so you can create new secondary access methods.

The purpose of a spatial index, such as R-tree, is to produce, during query processing, a candidate result set that is much smaller than the original set being searched (the table), as opposed to immediately finding the correct result set. The candidate result set that is found by traversing the R-tree index often contains false hits as well as true hits because the index uses enclosing boxes instead of the true shapes of the data objects. The false hits are eliminated by applying a more expensive, exact test to the small candidate set.

An R-tree index is inexact, but it is conservative. This means that a search that uses the R-tree index often retrieves too much information, but never too little. The final result of a search that uses the R-tree index is the same as a search that does not use the index or a search that uses an exact test on every object in the table.

Another way to look at an R-tree index is that it eliminates large amounts of data that could not possibly qualify in a search, without actually examining the data itself. It does this by eliminating data that falls outside boxes that enclose the area of interest.

R-tree indexes are dynamic. This means that an R-tree index maintains itself during updates, inserts, and deletes of the indexed table. In addition, you do not need to know anything about the amount of data or the range of values in the column to be indexed before you create an R-tree index.