R-link trees and concurrency

The basic R-tree index structure described in the previous topics 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, HCL 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 topics, 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.