ACM SIGMOD Anthology TODS dblp.uni-trier.de

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.


Joint ACM SIGMOD / IEEE Computer Society Anthology

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

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