H. T. Kung
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.
- 1 ASTRAHAN, M.M., ET AL. System R: Relational approach to database management.ACM Trans. Database Syst. 1, 2 (June 1976), 97-137. Google Scholar
Digital Library
- 2 BAYER, R., AND MCCREIGHT, E. Organization and maintenance of large ordered indexes. Acta Inf. I, 3 (1972), 173-189.Google ScholarDigital Library
- 3 BAYER, R., AND SCHKOLNICK, M. Concurrency of operations on B-trees. Acta Inf. 9, 1 (1977), 1- 21.Google ScholarDigital Library
- 4 DIJKSTRA, E.W. A Discipline of Programming. Prentice-Hall, Englewood Cliffs, N.J., 1976. Google ScholarDigital Library
- 5 DIJKSTRA, E.W., LAMPORT, L., MARTIN, A.J. SCHOLTEN, C.S., AND STEFFENS, E.F.M. On-thefly garbage collection: An exercise in cooperation. Commun. ACM 21, 11 (Nov. 1978), 966-976. Google ScholarDigital Library
- 6 ELLIS, C.S. Concurrent search and insertion in 2-3 trees. Tech. Rep. 78-05-01, Dep. Computer Science, Univ. Washington, Seattle, 1978.Google Scholar
- 7 ESWARAN, K.P., GRAY, J.N., LORIE, R.A., AND TRAIGER, I.L. The notions of consistency and predicate locks in a database system. Commun. ACM 19, 11 (Nov. 1976), 624-633. Google ScholarDigital Library
- 8 GRAY, J. Notes on database operating systems. Lecture Notes in Computer Science60: Operating Systems, Berlin, Germany, Feb. 1978, pp. 393-481. Google ScholarDigital Library
- 9 GU{BAS, L.J., AND SEDGEWICK, R. A dichromatic framework for balanced trees. Proc. 19th Ann. Syrup. Foundations of Computer Science, IEEE, 1978.Google Scholar
- 10 KNUTH, D.E. The Art of Computer Programming, vol. 3, Sorting and Searching. Addison- Wesley, Reading, Mass., 1973. Google ScholarDigital Library
- 11 KUNG, H.T. The Structure of Parallel Algorithms, vol. 19, Advances in Computers. Academic Press, New York, 1980. (Also available as a CMU Computer Science Dep. Tech. Rep., Aug. 1979.)Google Scholar
- 12 Kusc, H.T., AND PAPADIMITRIOU, C.H. An optimality theory of concurrency control for databases. Proc. ACM SIGMOD 1979 Int. Conf. Management of Data, 1979, pp. 116-126. Google ScholarDigital Library
- 13 KUNC, H.T., AND SONG, S.W. A parallel garbage collection algorithm and its correctness proof. Proc. 18th Ann. Syrup. Foundations of Computer Science, 1977, pp. 120-131.Google Scholar
- 14 LAMPORT, L. Proving the correctness of multiprocess programs. IEEE Trans. Softw. Eng. SE- 3, 2 (March I977), 125-143. Google ScholarDigital Library
- 15 LAMPORT, L. Concurrent reading and writing. Comrnun. ACM 20, 11 (Nov. 1977), 806-811. Google ScholarDigital Library
- 16 LEHMAN, P.L., AND YAO, S.B. Efficient locking for concurrent operations on B-trees. To appear in A CM Trans. Database Syst. Google ScholarDigital Library
- 17 MANNA, Z., AND WALDINGER, R. The logic of computer programming. IEEE Trans. Softw. Eng. SE-4, 3 (May 1978), 199-229.Google ScholarDigital Library
- 18 MILLER, R.E., AND SNYDER, L. Multiple access to B-trees. Proc. Conf. Information and Systems, Johns Hopkins Univ., Baltimore, Md., March 1978, preliminary version.Google Scholar
- 19 OWICKI, S. Axiomatic proof techniques for parallel program. Ph.D. Dissertation, Dep. Computer Science, Cornell Univ., Ithaca, N.Y., 1975. Google ScholarDigital Library
- 20 RIES, D.R., AND STONEBREAKER, M. Effects of locking granularity in a database management system. ACM Trans. Database Syst. 2, 3 (Sept. 1977), 233-246. Google ScholarDigital Library
- 21 SAMAra, B. B-trees in a system with multiple users. Inf. Process. Lett. 5, 4 (Oct. 1976), 107-112.Google Scholar
- 22 SWAN, R.J., FULL~R, S.H., ANY SIEWIORE~, D.P. CM*--A modular multi-microprocessor. Proc. AFIPS 1977 NCC, vol. 46, AFtPS Press, Arlington, Va., pp. 637-644.Google Scholar
- 23 WEDEKIND, S. On the selection of access paths in a data base system. In Data Base Management, J. W. Kimbie and K. L. Koffeman, Eds. North-Holland, New York, 1974, pp. 385-397.Google Scholar
- 24 WULF, W.A., AND BELL, C.G. C.mmp--A multi-mini-processor. Proc. AFIPS 1972 FJCC, vol. 41, AFIPS Press, Arlington, Va., pp. 765-777.Google Scholar
Index Terms
- Concurrent manipulation of binary search trees
Recommendations
Fast concurrent lock-free binary search trees
PPoPP '14: Proceedings of the 19th ACM SIGPLAN symposium on Principles and practice of parallel programmingWe present a new lock-free algorithm for concurrent manipulation of a binary search tree in an asynchronous shared memory system that supports search, insert and delete operations. In addition to read and write instructions, our algorithm uses (single-...
Efficient locking for concurrent operations on B-trees
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 ...
Efficient locking for concurrent operations on B-trees
Readings in database systems (3rd ed.)
Comments