The R-tree index

The two-dimensional R-tree index differs from the traditional hierarchical (one-dimensional) B-tree index. Spatial data is two dimensional, so you cannot use the B-tree index for spatial data. Similarly, you cannot use an R-tree index with nonspatial data. The R-tree access method organizes data in a tree-shaped structure with bounding boxes at the nodes.

A search using an R-tree index descends the tree to find objects in the general area of interest and perform tests on the objects themselves. An R-tree index eliminates the need to examine objects outside the area of interest. Without an R-tree index, a query would need to evaluate every object to find those that match the query criteria.

Informix uses an R-tree index to perform spatial queries. For more information about the Informix R-tree index, consult the IBM Informix Spatial DataBlade Module User's Guide, Version 8.21. The content of this manual is available in the IBM Informix Dynamic Server v11.10 and v11.50 Information Centers.

This manual can also be downloaded in PDF form from the following site:

In PostgreSQL, the R-tree index is implemented using the Generalized Search Tree (GiST) index infrastructure. For information on GiST indexing, see chapter 51 of the PostgreSQL 8.3 documentation.