Concurrency Control In a Dynamic Search Structure.

Udi Manber, Richard E. Ladner: Concurrency Control In a Dynamic Search Structure. ACM Trans. Database Syst. 9(3): 439-455(1984)

@article{DBLP:journals/tods/ManberL84,
  author    = {Udi Manber and
               Richard E. Ladner},
  title     = {Concurrency Control In a Dynamic Search Structure},
  journal   = {ACM Trans. Database Syst.},
  volume    = {9},
  number    = {3},
  year      = {1984},
  pages     = {439-455},
  ee        = {http://doi.acm.org/10.1145/1270.318576, db/journals/tods/ManberL84.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

A design of a data structure and efficient algorithms for concurrent manipulations of a dynamic search structure by independent user processes is presented in this paper. The algorithms include updating data, inserting new elements, and deleting elements. The algorithms support a high level of concurrency. Each of the operations listed above requires only constant amount of locking. In order to make the system even more efficient for the user processes, maintenance processes are introduced. The maintenance processes operate independently in the background to reorganize the data structure and "clean up" after the (more urgent) user processes. A proof of correctness of the algorithms is given and some experimental results and extensions are examined.

Copyright © 1984 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 ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/An3-1 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD2 or /dvd

BibTeX

Conference Version

Udi Manber, Richard E. Ladner: Concurrency Control in a Dynamic Search Structure. PODS 1982: 268-282 BibTeX

References

[1]: Rudolf Bayer, Mario Schkolnick: Concurrency of Operations on B-Trees. Acta Inf. 9: 1-21(1977) BibTeX
[2]: 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
[3]: Carla Schlatter Ellis: Concurrent Search and Insertion in AVL Trees. IEEE Trans. Computers 29(9): 811-817(1980) BibTeX
[4]: Carla Schlatter Ellis: Concurrent Search and Insertion in 2-3 Trees. Acta Inf. 14: 63-86,(1980) BibTeX
[5]: Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX
[6]: H. T. Kung, Philip L. Lehman: Concurrent Manipulation of Binary Search Trees. ACM Trans. Database Syst. 5(3): 354-382(1980) BibTeX
[7]: H. T. Kung, S. W. Song: An Efficient Parallel Garbage Collection System and Its Correctness Proof. FOCS 1977: 120-131 BibTeX
[8]: Yat-Sang Kwong, Derick Wood: A New Method for Concurrency in B-Trees. IEEE Trans. Software Eng. 8(3): 211-222(1982) BibTeX
[9]: Philip L. Lehman, S. Bing Yao: Efficient Locking for Concurrent Operations on B-Trees. ACM Trans. Database Syst. 6(4): 650-670(1981) BibTeX
[10]: ...
[11]: Udi Manber: Concurrent Maintenance of Binary Search Trees. IEEE Trans. Software Eng. 10(6): 777-784(1984) BibTeX
[12]: Behrokh Samadi: B-Trees in a System with Multiple Users. Inf. Process. Lett. 5(4): 107-112(1976) BibTeX

Referenced by

Otto Nurmi, Eljas Soisalon-Soininen: Uncoupling Updating and Rebalancing in Chromatic Binary Search Trees. PODS 1991: 192-198
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents
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
Peter Dadam, Vincent Y. Lum, U. Prädel, Gunter Schlageter: Selective Deferred Index Maintenance & Concurrency Control in Integrated Information Systems. VLDB 1985: 142-150

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]