|
 ABSTRACT
The B-tree and its variants have been found to be highly useful (both theoretically and in practice) for storing large amounts of information, 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.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
 |
1
|
M. M. Astrahan , M. W. Blasgen , D. D. Chamberlin , K. P. Eswaran , J. N. Gray , P. P. Griffiths , W. F. King , R. A. Lorie , P. R. McJones , J. W. Mehl , G. R. Putzolu , I. L. Traiger , B. W. Wade , V. Watson, System R: relational approach to database management, ACM Transactions on Database Systems (TODS), v.1 n.2, p.97-137, June 1976
[doi> 10.1145/320455.320457]
|
| |
2
|
BAYER, R., AND MCCREIGHT, E. Organization and maintenance of large ordered indexes. Acta Inf. I (1972), 173-189.
|
| |
3
|
BAYER, R., AND SCHKOLNICK, M. Concurrency of operations on B-trees. Acta Inf. 9 (1977), 1- 21.
|
| |
4
|
|
| |
5
|
DIJKSTRA, E.W. Cooperating sequential processes. In Programming Languages, F. Genuys, Ed. Academic Press, New York, 1968, pp. 43-112.
|
| |
6
|
ELLm, C.S. Concurrent search and insertion in 2-3 trees. Tech. Rep. 78-05-01, Dep. Computer Science, Univ. Washington, Seattle, May 1978.
|
| |
6a
|
GUIBAB, L.J., AND SEDGEWICK, R. A dichromatic framework for balanced trees. In Proc. 19th Ann. Syrup. Foundation of Computer Science, IEEE, 1978.
|
| |
7
|
|
| |
8
|
|
| |
9
|
KUNG, H.T., AND SONG, S.W. A parallel garbage collection algorithm and its correctness proof. In Proc. 18th Ann. Symp. Foundations of Computer Science, IEEE, Oct. 1977, pp. 120-131.
|
| |
10
|
KwoNa, Y.S., AND WOOD, D. Concurrency in B- and T-trees. In preparation.
|
| |
11
|
|
| |
12
|
MILLER, R., AND SNYDER, L. Multiple access to B-trees. In Proc. Conf. Information Sciences and Systems (preliminary version), Johns Hopkins Univ., Baltimore, March 1978.
|
| |
13
|
SAMADI, B. B-trees in a system with multiple users. Inf. Process. Lett. 5, 4 (Oct. 1976), 107-112.
|
| |
14
|
|
| |
15
|
WEDEKIND, H. On the selection of access paths in a data base system. In Data Base Management, J.W. Klimbie and K.L. Koffeman, Eds. North-Holland, Amsterdam, 1974, pp. 385-397.
|
CITED BY 98
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
O. Nurmi , E. Soisalon-Soininen , D. Wood, Concurrency control in database structures with relaxed balance, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.170-176, March 23-25, 1987, San Diego, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
John Turek , Dennis Shasha , Sundeep Prakash, Locking without blocking: making lock based concurrent data structure algorithms nonblocking, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.212-222, June 02-05, 1992, San Diego, California, United States
|
|
|
|
|
|
|
|
|
Wilson C. Hsieh , M. Frans Kaashoek , William E. Weihl, Dynamic computation migration in DSM systems, Proceedings of the 1996 ACM/IEEE conference on Supercomputing (CDROM), p.44-es, January 01-01, 1996, Pittsburgh, Pennsylvania, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
C. Beeri , P. A. Bernstein , N. Goodman , M. Y. Lai , D. E. Shasha, A concurrency control theory for nested transactions (Preliminary Report), Proceedings of the second annual ACM symposium on Principles of distributed computing, p.45-62, August 17-19, 1983, Montreal, Quebec, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Takashi Nakamura , Toshiyuki Iwamiya , Masahiro Yoshida , Yuichi Matsuo , Masahiro Fukuda, Simulation of the 3 dimensional cascade flow with numerical wind tunnel (NWT), Proceedings of the 1996 ACM/IEEE conference on Supercomputing (CDROM), p.47-es, January 01-01, 1996, Pittsburgh, Pennsylvania, United States
|
|
|
|
|
|
|
|
|
|
|
|
John MacCormick , Nick Murphy , Marc Najork , Chandramohan A. Thekkath , Lidong Zhou, Boxwood: abstractions as the foundation for storage infrastructure, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.8-8, December 06-08, 2004, San Francisco, CA
|
|
|
|
|
|
|
|
|
Peter Dadam , Vincent Y. Lum , U. Prädel , Gunter Schlageter, Selective deferred index maintenance & concurrency control in integrated information systems, Proceedings of the 11th international conference on Very Large Data Bases, p.142-150, August 21-23, 1985, Stockholm, Sweden
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Matthias Brantner , Daniela Florescu , David Graf , Donald Kossmann , Tim Kraska, Building a database on S3, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Tuukka K. Haapasalo , Ibrahim M. Jaluta , Seppo S. Sippu , Eljas O. Soisalon-Soininen, Concurrency control and recovery for multiversion database structures, Proceeding of the 2nd PhD workshop on Information and knowledge management, October 30-30, 2008, Napa Valley, California, USA
|
|
|
|
|
|
Andrey Ermolinskiy , Daekyeong Moon , Byung-Gon Chun , Scott Shenker, Minuet: rethinking concurrency control in storage area networks, Proccedings of the 7th conference on File and stroage technologies, p.311-324, February 24-27, 2009, San Francisco, California
|
|
|
Ryan Johnson , Ippokratis Pandis , Nikos Hardavellas , Anastasia Ailamaki , Babak Falsafi, Shore-MT: a scalable storage manager for the multicore era, Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, March 24-26, 2009, Saint Petersburg, Russia
|
|
|
|
|
|
Xiaoyong Chai , Ba-Quy Vuong , AnHai Doan , Jeffrey F. Naughton, Efficiently incorporating user feedback into information extraction and integration programs, Proceedings of the 35th SIGMOD international conference on Management of data, June 29-July 02, 2009, Providence, Rhode Island, USA
|
INDEX TERMS
Primary Classification:
H.
Information Systems
H.2
DATABASE MANAGEMENT
H.2.4
Systems
Subjects:
Concurrency
Additional Classification:
G.
Mathematics of Computing
G.2
DISCRETE MATHEMATICS
G.2.2
Graph Theory
Subjects:
Trees
General Terms:
Algorithms,
Design,
Theory
Keywords:
B-tree,
concurrenct algorithms,
concurrency controls,
consistencey,
correctness,
data structures,
database,
index organizations,
locking protocols,
multiway search trees
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf