ACM SIGMOD Anthology TODS dblp.uni-trier.de

Concurrent Manipulation of Binary Search Trees.

H. T. Kung, Philip L. Lehman: Concurrent Manipulation of Binary Search Trees. ACM Trans. Database Syst. 5(3): 354-382(1980)
@article{DBLP:journals/tods/KungL80,
  author    = {H. T. Kung and
               Philip L. Lehman},
  title     = {Concurrent Manipulation of Binary Search Trees},
  journal   = {ACM Trans. Database Syst.},
  volume    = {5},
  number    = {3},
  year      = {1980},
  pages     = {354-382},
  ee        = {http://doi.acm.org/10.1145/320613.320619, db/journals/tods/KungL80.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

The concurrent manipulation of a binary search tree is considered in this paper. The systems presented can support any number of concurrent processes which perform searching, insertion, deletion, and rotation (reorganization) on the tree, but allow any process to lock only a constant number of nodes at any time. Also, in the systems, searches are essentially never blocked. The concurrency control techniques introduced in the paper include the use of special nodes and pointers to redirect searches, and the use of copies of sections of the tree to introduce many changes simultaneously and therefore avoid unpredictable interleaving. Methods developed in this paper may provide new insights into other problems in the area of concurrent database manipulation.

Copyright © 1980 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: A Discipline of Programming. Prentice-Hall 1976
BibTeX
[5]
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
[6]
Carla Schlatter Ellis: Concurrent Search and Insertion in 2-3 Trees. Acta Inf. 14: 63-86,(1980) BibTeX
[7]
Kapali P. Eswaran, Jim Gray, Raymond A. Lorie, Irving L. Traiger: The Notions of Consistency and Predicate Locks in a Database System. Commun. ACM 19(11): 624-633(1976) BibTeX
[8]
Jim Gray: Notes on Data Base Operating Systems. Advanced Course: Operating Systems 1978: 393-481 BibTeX
[9]
Leonidas J. Guibas, Robert Sedgewick: A Dichromatic Framework for Balanced Trees. FOCS 1978: 8-21 BibTeX
[10]
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX
[11]
H. T. Kung: The Structure of Parallel Algorithms. Advances in Computers 19: 65-112(1980) BibTeX
[12]
H. T. Kung, Christos H. Papadimitriou: An Optimality Theory of Concurrency Control for Databases. SIGMOD Conference 1979: 116-126 BibTeX
[13]
H. T. Kung, S. W. Song: An Efficient Parallel Garbage Collection System and Its Correctness Proof. FOCS 1977: 120-131 BibTeX
[14]
Leslie Lamport: Proving the Correctness of Multiprocess Programs. IEEE Trans. Software Eng. 3(2): 125-143(1977) BibTeX
[15]
Leslie Lamport: Concurrent Reading and Writing. Commun. ACM 20(11): 806-811(1977) BibTeX
[16]
Philip L. Lehman, S. Bing Yao: Efficient Locking for Concurrent Operations on B-Trees. ACM Trans. Database Syst. 6(4): 650-670(1981) BibTeX
[17]
Zohar Manna, Richard J. Waldinger: The Logic of Computer Programming. IEEE Trans. Software Eng. 4(3): 199-229(1978) BibTeX
[18]
...
[19]
...
[20]
Daniel R. Ries, Michael Stonebraker: Effects of Locking Granularity in a Database Management System. ACM Trans. Database Syst. 2(3): 233-246(1977) BibTeX
[21]
Behrokh Samadi: B-Trees in a System with Multiple Users. Inf. Process. Lett. 5(4): 107-112(1976) BibTeX
[22]
...
[23]
...
[24]
...

Referenced by

  1. Rajeev Rastogi, S. Seshadri, Philip Bohannon, Dennis W. Leinbaugh, Abraham Silberschatz, S. Sudarshan: Logical and Physical Versioning in Main Memory Databases. VLDB 1997: 86-95
  2. Marcel Kornacker, C. Mohan, Joseph M. Hellerstein: Concurrency and Recovery in Generalized Search Trees. SIGMOD Conference 1997: 62-72
  3. V. Srinivasan, Michael J. Carey: Performance of B+ Tree Concurrency Algorithms. VLDB J. 2(4): 361-406(1993)
  4. John Turek, Dennis Shasha, Sundeep Prakash: Locking without Blocking: Making Lock Based Concurrent Data Structure Algorithms Nonblocking. PODS 1992: 212-222
  5. Otto Nurmi, Eljas Soisalon-Soininen: Uncoupling Updating and Rebalancing in Chromatic Binary Search Trees. PODS 1991: 192-198
  6. Theodore Johnson, Dennis Shasha: A Framework for the Performance Analysis of Concurrent B-tree Algorithms. PODS 1990: 273-287
  7. Ada Wai-Chee Fu, Tiko Kameda: Concurrency Control of Nested Transactions Accessing B-Trees. PODS 1989: 270-285
  8. Dennis Shasha, Nathan Goodman: Concurrent Search Structure Algorithms. ACM Trans. Database Syst. 13(1): 53-90(1988)
  9. Vladimir Lanin, Dennis Shasha: Concurrent Set Manipulation without Locking. PODS 1988: 211-220
  10. Thanasis Hadzilacos, Vassos Hadzilacos: Transaction Synchronisation in Object Bases. PODS 1988: 193-200
  11. Carla Schlatter Ellis: Concurrency in Linear Hashing. ACM Trans. Database Syst. 12(2): 195-217(1987)
  12. Otto Nurmi, Eljas Soisalon-Soininen, Derick Wood: Concurrency Control in Database Structures with Relaxed Balance. PODS 1987: 170-176
  13. Alexandros Biliris: Operation Specific Locking in B-Trees. PODS 1987: 159-169
  14. Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
    Contents
  15. Nathan Goodman, Dennis Shasha: Semantically-based Concurrency Control for Search Structures. PODS 1985: 8-19
  16. Carla Schlatter Ellis: Concurrency and Linear Hashing. PODS 1985: 1-7
  17. Udi Manber, Richard E. Ladner: Concurrency Control In a Dynamic Search Structure. ACM Trans. Database Syst. 9(3): 439-455(1984)
  18. Ray Ford, Jim Calhoun: Concurrency Control Mechanisms and the Serializability of Concurrent Tree Algorithms. PODS 1984: 51-60
  19. Udi Manber, Richard E. Ladner: Concurrency Control in a Dynamic Search Structure. PODS 1982: 268-282
  20. Philip L. Lehman, S. Bing Yao: Efficient Locking for Concurrent Operations on B-Trees. ACM Trans. Database Syst. 6(4): 650-670(1981)
  21. H. T. Kung, John T. Robinson: On Optimistic Methods for Concurrency Control. ACM Trans. Database Syst. 6(2): 213-226(1981)
  22. H. T. Kung, Christos H. Papadimitriou: An Optimality Theory of Concurrency Control for Databases. SIGMOD Conference 1979: 116-126
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:44 2008