Search with an R-tree index

The simplest kind of search that uses an R-tree access method is for objects that overlap a search object. For example, you might want to search for all the polygons stored in the column of a table that overlap a specified polygon. To use the R-tree access method to improve the performance of this type of search, you must create an R-tree index on the table column that contains the polygons, and then you must specify a function that checks for overlap (listed in the operator class definition as a strategy function) in the WHERE clause of the query statement. Operator classes and strategy functions are described in more detail in About operator classes.

The R-tree secondary access method uses the bounding box of the search object to guide the search. The access method begins a search at the root of the R-tree index structure. The access method compares the bounding box of the search object to the bounding boxes stored in the index entries of the root page. All subtrees whose bounding boxes overlap the search bounding box must be searched, because they might contain qualifying data. Any number of subtrees might need to be searched. The access method then recursively applies the same process to each qualifying subtree. Subtrees whose bounding boxes do not overlap are skipped; this is where the R-tree access method saves search time and work. The access method uses the appropriate strategy function to test for overlap of bounding box entries in branch index pages.

When the search encounters a leaf page, it applies the appropriate strategy function to each key on the leaf page. The strategy function tests for bounding box overlap between the search object's bounding box and the key's bounding box. If this test passes, the strategy function then applies an exact overlap test between the actual search object and the actual key. Keys that qualify according to the strategy function satisfy the query restriction being tested because of this final exact test and result in the set of rows that are returned from the original query.