Concurrent Hilbert R-link tree

In this paper, we develop new concurrent algorithms for Hilbert R-link tree in which a search operation (window query or exact-match query) latches one node at time while an update operation (insert or delete) latches two pages at a time as in concurrent B-tree algorithms. An update operation uses latch-coupling with U latches during tree traversal. Update operations and tree-structure-modifications are executed in one pass over the Hilbert R-link tree from the root page down to the leaf-page level. To simplify recovery, each tree-structure-modification latches two pages on a single level of the tree, executed as an atomic action, and logged using a single redo-only log record. The algorithms keep the Hilbert R-link tree balanced during normal processing and after transaction aborts (or system failure) to guarantee logarithmic search path.