1981/12/01 by Philip L. Lehman, S. Bing Yao · 1 citation
Computer Science · #Distributed systems and fault tolerance #Advanced Data Storage Technologies #Parallel Computing and Optimization Techniques
paper · pdf · doi:10.1145/319628.319663
openalex publication_date 1981/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
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.