Efficient Locking for Concurrent Operations on B-Trees
by Philip L. Lehman, S. Bing Yao
url show details
Details
number: | 4 | volume: | 6 | 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. | type: | misc | pages: | 650--670 | journal: | ACM Transactions on Database Systems | year: | 1981 | month: | dec |
|
|
You need to log in to add tags and post comments.