Efficient locking for concurrent operations on B-trees

TLDR

B‑trees and their variants are widely used for storing large data sets, especially on secondary storage devices. The study addresses how to overcome the difficulty of concurrent operations on B‑trees using a practical storage model. The authors add a single link pointer to each node to allow recovery from concurrent modifications and provide an informal correctness proof. Their locking scheme is simpler than previous approaches, requiring no read locks and locking only a small constant number of nodes per update.

Abstract

The B-tree and its variants have been found to be highly useful (both theoretically and in practice) for storing large amounts of information, especially on secondary storage devices. We examine the problem of overcoming the inherent difficulty of concurrent operations on such structures, using a practical storage model. A single additional “link” pointer in each node allows a process to easily recover from tree modifications performed by other concurrent processes. Our solution compares favorably with earlier solutions in that the locking scheme is simpler (no read-locks are used) and only a (small) constant number of nodes are locked by any update process at any given time. An informal correctness proof for our system is given.