Efficient Locking for Concurrent Operations on B-Trees.
Philip L. Lehman, S. Bing Yao:
Efficient Locking for Concurrent Operations on B-Trees.
ACM Trans. Database Syst. 6(4): 650-670(1981)@article{DBLP:journals/tods/LehmanY81,
author = {Philip L. Lehman and
S. Bing Yao},
title = {Efficient Locking for Concurrent Operations on B-Trees},
journal = {ACM Trans. Database Syst.},
volume = {6},
number = {4},
year = {1981},
pages = {650-670},
ee = {http://doi.acm.org/10.1145/319628.319663, db/journals/tods/LehmanY81.html},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
The B-tree and its variants have been found to be highly useful (both theoretically
and in practice) for storing large amounts ofinformation, 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.
Copyright © 1981 by the ACM,
Inc., used by permission. Permission to make
digital or hard copies is granted provided that
copies are not made or distributed for profit or
direct commercial advantage, and that copies show
this notice on the first page or initial screen of
a display along with the full citation.
CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ...
DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...
BibTeX
References
- [1]
- Morton M. Astrahan, Mike W. Blasgen, Donald D. Chamberlin, Kapali P. Eswaran, Jim Gray, Patricia P. Griffiths, W. Frank King III, Raymond A. Lorie, Paul R. McJones, James W. Mehl, Gianfranco R. Putzolu, Irving L. Traiger, Bradford W. Wade, Vera Watson:
System R: Relational Approach to Database Management.
ACM Trans. Database Syst. 1(2): 97-137(1976) BibTeX
- [2]
- Rudolf Bayer, Edward M. McCreight:
Organization and Maintenance of Large Ordered Indices.
Acta Inf. 1: 173-189(1972) BibTeX
- [3]
- Rudolf Bayer, Mario Schkolnick:
Concurrency of Operations on B-Trees.
Acta Inf. 9: 1-21(1977) BibTeX
- [4]
- Edsger W. Dijkstra, Leslie Lamport, Alain J. Martin, Carel S. Scholten, Elisabeth F. M. Steffens:
On-the-Fly Garbage Collection: An Exercise in Cooperation.
Commun. ACM 21(11): 966-975(1978) BibTeX
- [5]
- ...
- [6]
- Carla Schlatter Ellis:
Concurrent Search and Insertion in 2-3 Trees.
Acta Inf. 14: 63-86,(1980) BibTeX
- [6a]
- Leonidas J. Guibas, Robert Sedgewick:
A Dichromatic Framework for Balanced Trees.
FOCS 1978: 8-21 BibTeX
- [7]
- Donald E. Knuth:
The Art of Computer Programming, Volume III: Sorting and Searching.
Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX
- [8]
- H. T. Kung, Philip L. Lehman:
Concurrent Manipulation of Binary Search Trees.
ACM Trans. Database Syst. 5(3): 354-382(1980) BibTeX
- [9]
- H. T. Kung, S. W. Song:
An Efficient Parallel Garbage Collection System and Its Correctness Proof.
FOCS 1977: 120-131 BibTeX
- [10]
- ...
- [11]
- Leslie Lamport:
Concurrent Reading and Writing.
Commun. ACM 20(11): 806-811(1977) BibTeX
- [12]
- ...
- [13]
- Behrokh Samadi:
B-Trees in a System with Multiple Users.
Inf. Process. Lett. 5(4): 107-112(1976) BibTeX
- [14]
- Guy L. Steele Jr.:
Multiprocessing Compactifying Garbage Collection.
Commun. ACM 18(9): 495-508(1975) BibTeX
- [15]
- Hartmut Wedekind:
On the Selection of Access Paths in a Data Base System.
IFIP Working Conference Data Base Management 1974: 385-398 BibTeX
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 20:11:46 2008
