A concurrent and recoverable restructuring method for R-tree

摘要

R-tree is multidimensional index structure used in spatial database systems. In R-trees, a spatial object is indexed by a minimum-bounding box that contains the object. R-tree structure modifications such as page split or deletion, and minimum-bounding-box resizing arc still presenting a challenge to concurrency and recovery. We present a new restructuring method for R-tree to enhance concurrency and to simplify recovery. In our method, we assume that fetching and updating transactions use latch-coupling protocol with S latches to traverse the R-tree from the root node to reach leaf-level nodes, and we employ a strict and relaxed index consistency approaches to handle R-tree structure modifications.