We consider the recoverability of traditional R-tree index structures under concurrent updating transactions, an important issue that is neglected or treated inadequately in many proposals of R-tree concurrency control. We present two solutions to ARIES-based recovery of transactions on R-trees. These assume a standard fine-grained single-version update model with physiological write-ahead logging and steal-and-no-force buffering where records with uncommitted updates by a transaction may migrate from their original page to another page due to structure modifications caused by other transactions. Both solutions guarantee that an R-tree will remain in a consistent and balanced state in the presence of any number of concurrent forward-rolling and (totally or partially) backward-rolling multiaction transactions and in the event of process failures and system crashes. One solution maintains the R-tree in a strictly consistent state in which the bounding rectangles of pages are as tight as possible, while in the other solution this requirement is relaxed. In both solutions only a small constant number of simultaneous exclusive latches (write latches) are needed, and in the solution that only maintains relaxed consistency also the number of simultaneous nonexclusive latches is similarly limited. In both solutions, deletions are handled uniformly with insertions, and a logarithmic insertion-path length is maintained under all circumstances.

The multiversion B+-tree (MVBT) by Becker et al. assumes a single-data-item update model in which each new version created for a data item is given a timestamp that is unique across the entire MVBT. In this paper, we extend the MVBT model with multi-action transactions such that all (final) data-item versions created by a transaction are given the same timestamp. We show that the MVBT algorithms can be modified to work in a setting in which multiple readonly transactions and a single updating transaction operate concurrently in snapshot isolation on the MVBT, without compromising the asymptotically optimal time complexity of key inserts, key deletes, and key-range scans on any version. The structural consistency and balance of the MVBT is guaranteed by short-duration latching of pages, redo-only logging of structure modifications (version splits, key splits and page merges), and redo-undo logging of key insertions and deletions. The redo pass of our ARIES-based restart-recovery algorithm always produces a structurally consistent and balanced MVBT on which any undo action by a backward-rolling updating transaction can be performed logically if a physical undo is not possible. The standard steal-and-no-force buffering policy is assumed.

Modern database applications increasingly often require access to historical versions of the database. Storing such multiversion data in a single-version B+ -tree database index is inefficient, especially for key-range queries. In this article, we present an index structure called the concurrent multiversion B+ -tree (CMVBT) for efficiently storing and querying multiversion data.

We develop new algorithms for the management of transactions in a page-shipping client-server database system in which the physical database is organized as a sparse B-tree index. Our starvation-free fine-grained locking protocol combines adaptive callbacks with key-range locking and guarantees repeatable-read-level isolation (i.e., serializability) for transactions containing any number of record insertions, record deletions, and key-range scans. Partial and total rollbacks of client transactions are performed by the client. Each structure modification such as a page split or merge is defined as an atomic action that affects only two levels of the B-tree and is logged using a single redo-only log record, so that the modification never needs to be undone during transaction rollback or restart recovery. The steal-and-no-force buffering policy is applied by the server when flushing updated pages onto disk and by the clients when shipping updated data pages to the server, while pages involved in a structure modification are forced to the server when the modification is finished. The server performs the restart recovery from client and system failures using an ARIES/CSA-based recovery protocol. Our algorithms avoid accessing stale data but allow a data page to be updated by one client transaction and read by many other client transactions simultaneously, and updates may migrate from a data page to another in structure modifications caused by other transactions while the updating transaction is still active.