R-Link Trees and Concurrency

The basic R-tree index structure described in the previous sections works well in a single-user environment but might run into problems if multiple users search and update the index concurrently. R-tree indexes require a particular type of locking during page splits to preserve the integrity of the index structure and ensure correct results from queries. For example, while a page is being split, it is necessary to hold locks on all pages up to and including the root page. This locking behavior is problematic in a concurrent environment. To solve this problem, Informix uses a modified structure called an R-link tree instead of the basic R-tree.

R-link trees are similar to the R-tree structure described in the preceding sections, with the following two key differences:

• All the pages at the same level in the index structure contain a pointer to their right sibling (except for the rightmost page, which has a null pointer). This creates a single list of right-pointing links that includes every page in a particular level.

  When a page splits and a new page is created, the new page is inserted into the list of right-pointing links directly to the right of the old page.

  This sibling relationship between pages has no semantic or spatial meaning and is not used in a search of the index. It is only used to keep the index structure consistent and to maintain the correct functioning of the index while it allows concurrent access and updates.

• Each page in the index is assigned a sequence number that is unique within the tree. Each index entry in a root or branch page includes the expected sequence number of its child page, in addition to the information listed in Hierarchical Index Structure.

  When a page splits, the new right sibling page is assigned the old page's sequence number, and the old page receives a new sequence number.

The R-link structure allows the R-tree access method to perform index operations without holding locks on pages that might be needed again later. The combination of right-pointing links and sequence numbers lets the R-tree access method detect page splits made by other users and correctly find all the needed pages.