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
Referenced by
- Seppo Sippu, Eljas Soisalon-Soininen:
A Theory of Transactions on Recoverable Search Trees.
ICDT 2001: 83-98
- Nagavamsi Ponnekanti, Hanuma Kodavalla:
Online Index Rebuild.
SIGMOD Conference 2000: 529-538
- Dennis Shasha:
Review - Efficient Locking for Concurrent Operations on B-Trees.
ACM SIGMOD Digital Review 1: (1999)
- Haruo Yokota, Yasuhiko Kanemasa, Jun Miyazaki:
Fat-Btree: An Update-Conscious Parallel Directory Structure.
ICDE 1999: 448-457
- Tei-Wei Kuo, Chih-Hung Wei, Kam-yiu Lam:
Real-Time Data Access Control on B-Tree Index Structures.
ICDE 1999: 458-467
- Rasa Bliujute, Simonas Saltenis, Giedrius Slivinskas, Christian S. Jensen:
Developing a DataBlade for a New Index.
ICDE 1999: 314-323
- Sungchae Lim, Yoon-Joon Lee, Myoung-Ho Kim:
A Restructuring Method for the Concurrent B+-Tree Based on Semantic Consistency.
DASFAA 1999: 229-236
- Richard T. Snodgrass:
Reminiscences on Influential Papers.
SIGMOD Record 27(1): 54-57(1998)
- Lukas Relly, Heiko Schuldt, Hans-Jörg Schek:
Exporting Database Functionality - The CONCERT Way.
IEEE Data Eng. Bull. 21(3): 43-51(1998)
- Volker Gaede, Oliver Günther:
Multidimensional Access Methods.
ACM Comput. Surv. 30(2): 170-231(1998)
- David B. Lomet, Betty Salzberg:
Concurrency and Recovery for Index Trees.
VLDB J. 6(3): 224-240(1997)
- Georgios Evangelidis, David B. Lomet, Betty Salzberg:
The hB-Pi-Tree: A Multi-Attribute Index Supporting Concurrency, Recovery and Node Consolidation.
VLDB J. 6(1): 1-25(1997)
- Paul M. Bober, Michael J. Carey:
Indexing for Multiversion Locking: Alternatives and Performance Evaluation.
IEEE Trans. Knowl. Data Eng. 9(1): 68-84(1997)
- André Eickler, Alfons Kemper, Donald Kossmann:
Finding Data in the Neighborhood.
VLDB 1997: 336-345
- Markos Zaharioudakis, Michael J. Carey:
Highly Concurrent Cache Consistency for Indices in Client-Server Database Systems.
SIGMOD Conference 1997: 50-61
- Marcel Kornacker, C. Mohan, Joseph M. Hellerstein:
Concurrency and Recovery in Generalized Search Trees.
SIGMOD Conference 1997: 62-72
- Kerttu Pollari-Malmi, Eljas Soisalon-Soininen, Tatu Ylönen:
Concurrency Control in B-Trees with Batch Updates.
IEEE Trans. Knowl. Data Eng. 8(6): 975-984(1996)
- Marcel Kornacker, Douglas Banks:
High-Concurrency Locking in R-Trees.
VLDB 1995: 134-145
- Joseph M. Hellerstein, Jeffrey F. Naughton, Avi Pfeffer:
Generalized Search Trees for Database Systems.
VLDB 1995: 562-573
- Brajesh Goyal, Jayant R. Haritsa, S. Seshadri, V. Srinivasan:
Index Concurrency Control in Firm Real-Time Database Systems.
VLDB 1995: 146-157
- Georgios Evangelidis, David B. Lomet, Betty Salzberg:
The hBP-tree: A Modified hB-tree Supporting Concurrency, Recovery and Node Consolidation.
VLDB 1995: 551-561
- V. W. Setzer, Andrea Zisman:
New Concurrency Control Algorithms for Accessing and Compacting B-Trees.
VLDB 1994: 238-248
- Paul M. Bober, Michael J. Carey:
Indexing Alternatives for Multiversion Locking.
EDBT 1994: 145-158
- V. Srinivasan, Michael J. Carey:
Performance of B+ Tree Concurrency Algorithms.
VLDB J. 2(4): 361-406(1993)
- Theodore Johnson, Dennis Shasha:
The Performance of Current B-Tree Algorithms.
ACM Trans. Database Syst. 18(1): 51-101(1993)
- Georgios Evangelidis, Betty Salzberg:
Using the Holy Brick Tree for Spatial Data in General Purpose DBMSs.
IEEE Data Eng. Bull. 16(3): 34-39(1993)
- David B. Lomet, Betty Salzberg:
Exploiting A History Database for Backup.
VLDB 1993: 380-390
- Theodore Johnson, Padmashree Krishna:
Lazy Updates for Distributed Search Structure.
SIGMOD Conference 1993: 337-346
- Margo I. Seltzer:
Transaction Support in a Log-Structured File System.
ICDE 1993: 503-510
- John K. Lee:
B-Tree Concurrency Control Algorithm for Nested Transaction Systems.
DASFAA 1993: 205-215
- C. Mohan, Frank Levine:
ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging.
SIGMOD Conference 1992: 371-380
- David B. Lomet, Betty Salzberg:
Access Method Concurrency with Recovery.
SIGMOD Conference 1992: 351-360
- John Turek, Dennis Shasha, Sundeep Prakash:
Locking without Blocking: Making Lock Based Concurrent Data Structure Algorithms Nonblocking.
PODS 1992: 212-222
- Mark Sullivan, Michael A. Olson:
An Index Implementation Supporting Fast Recovery for the POSTGRES Storage System.
ICDE 1992: 293-300
- Ragaa Ishak:
Semantically Consistent Schedules for Efficient and Concurrent B-Tree Restructuring.
ICDE 1992: 184-191
- V. Srinivasan, Michael J. Carey:
Performance of On-Line Index Construction Algorithms.
EDBT 1992: 293-309
- Ashok M. Joshi:
Adaptive Locking Strategies in a Multi-node Data Sharing Environment.
VLDB 1991: 181-191
- V. Srinivasan, Michael J. Carey:
Performance of B-Tree Concurrency Algorithms.
SIGMOD Conference 1991: 416-425
- Pyung-Chul Kim, Hwan-Ik Choi, Yoon-Joon Lee, Myung-Joon Kim:
Design and Implementation of the Multiuser Index-based Data Access System.
DASFAA 1991: 156-164
- David B. Lomet, Betty Salzberg:
The hB-Tree: A Multiattribute Indexing Method with Good Guaranteed Performance.
ACM Trans. Database Syst. 15(4): 625-658(1990)
- Theodore Johnson, Dennis Shasha:
A Framework for the Performance Analysis of Concurrent B-tree Algorithms.
PODS 1990: 273-287
- George P. Copeland, Michael J. Franklin, Gerhard Weikum:
Uniform Object Management.
EDBT 1990: 253-268
- Ada Wai-Chee Fu, Tiko Kameda:
Concurrency Control of Nested Transactions Accessing B-Trees.
PODS 1989: 270-285
- David B. Lomet, Betty Salzberg:
A Robust Multi-Attribute Search Structure.
ICDE 1989: 296-304
- Jeffrey D. Ullman:
Principles of Database and Knowledge-Base Systems, Volume II.
Computer Science Press 1989, ISBN 0-7167-8162-X
Contents - Dennis Shasha, Nathan Goodman:
Concurrent Search Structure Algorithms.
ACM Trans. Database Syst. 13(1): 53-90(1988)
- Vladimir Lanin, Dennis Shasha:
Concurrent Set Manipulation without Locking.
PODS 1988: 211-220
- Thanasis Hadzilacos, Vassos Hadzilacos:
Transaction Synchronisation in Object Bases.
PODS 1988: 193-200
- Edward Omiecinski:
Concurrent Storage Structure Conversion: from B+ Tree to Linear Hash File.
ICDE 1988: 589-596
- Carla Schlatter Ellis:
Concurrency in Linear Hashing.
ACM Trans. Database Syst. 12(2): 195-217(1987)
- Otto Nurmi, Eljas Soisalon-Soininen, Derick Wood:
Concurrency Control in Database Structures with Relaxed Balance.
PODS 1987: 170-176
- Alexandros Biliris:
Operation Specific Locking in B-Trees.
PODS 1987: 159-169
- Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman:
Concurrency Control and Recovery in Database Systems.
Addison-Wesley 1987, ISBN 0-201-10715-5
Contents - Meichun Hsu, Wei-Pang Yang:
Concurrent Operations in Extendible Hashing.
VLDB 1986: 241-247
- Peter Dadam, Vincent Y. Lum, U. Prädel, Gunter Schlageter:
Selective Deferred Index Maintenance & Concurrency Control in Integrated Information Systems.
VLDB 1985: 142-150
- Yehoshua Sagiv:
Concurrent Operations on B-Trees with Overtaking.
PODS 1985: 28-37
- Nathan Goodman, Dennis Shasha:
Semantically-based Concurrency Control for Search Structures.
PODS 1985: 8-19
- Carla Schlatter Ellis:
Concurrency and Linear Hashing.
PODS 1985: 1-7
- Udi Manber, Richard E. Ladner:
Concurrency Control In a Dynamic Search Structure.
ACM Trans. Database Syst. 9(3): 439-455(1984)
- Ray Ford, Jim Calhoun:
Concurrency Control Mechanisms and the Serializability of Concurrent Tree Algorithms.
PODS 1984: 51-60
- Carla Schlatter Ellis:
Extendible Hashing for Concurrent Operations and Distributed Data.
PODS 1983: 106-116
- Udi Manber, Richard E. Ladner:
Concurrency Control in a Dynamic Search Structure.
PODS 1982: 268-282
- H. T. Kung, John T. Robinson:
On Optimistic Methods for Concurrency Control.
ACM Trans. Database Syst. 6(2): 213-226(1981)
- H. T. Kung, Philip L. Lehman:
Concurrent Manipulation of Binary Search Trees.
ACM Trans. Database Syst. 5(3): 354-382(1980)
- Yat-Sang Kwong, Derick Wood:
On B-Trees: Routing Schemes and Concurrency.
SIGMOD Conference 1980: 207-211
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 18:38:47 2008