Efficient locking for concurrent operations on B-trees
- 1 December 1981
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Database Systems
- Vol. 6 (4), 650-670
- https://doi.org/10.1145/319628.319663
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.Keywords
This publication has 9 references indexed in Scilit:
- Concurrent manipulation of binary search treesACM Transactions on Database Systems, 1980
- On-the-fly garbage collectionCommunications of the ACM, 1978
- Concurrent reading and writingCommunications of the ACM, 1977
- An efficient parallel garbage collection system and ITS correctness proofPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1977
- Concurrency of operations on B-treesActa Informatica, 1977
- B-trees in a system with multiple usersInformation Processing Letters, 1976
- System RACM Transactions on Database Systems, 1976
- Multiprocessing compactifying garbage collectionCommunications of the ACM, 1975
- Organization and maintenance of large ordered indexesActa Informatica, 1972