Concurrent manipulation of binary search trees

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.

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, 3 (1972), 173-189.
• 3: BAYER, R., AND SCHKOLNICK, M. Concurrency of operations on B-trees. Acta Inf. 9, 1 (1977), 1- 21.
• 4: Edsger Wybe Dijkstra, A Discipline of Programming, Prentice Hall PTR, Upper Saddle River, NJ, 1997
• 5: Edsger W. Dijkstra , Leslie Lamport , A. J. Martin , C. S. Scholten , E. F. M. Steffens, On-the-fly garbage collection: an exercise in cooperation, Communications of the ACM, v.21 n.11, p.966-975, Nov. 1978 [doi>10.1145/359642.359655]
• 6: ELLIS, C.S. Concurrent search and insertion in 2-3 trees. Tech. Rep. 78-05-01, Dep. Computer Science, Univ. Washington, Seattle, 1978.
• 7: K. P. Eswaran , J. N. Gray , R. A. Lorie , I. L. Traiger, The notions of consistency and predicate locks in a database system, Communications of the ACM, v.19 n.11, p.624-633, Nov. 1976 [doi>10.1145/360363.360369]
• 8: Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
• 9: GU{BAS, L.J., AND SEDGEWICK, R. A dichromatic framework for balanced trees. Proc. 19th Ann. Syrup. Foundations of Computer Science, IEEE, 1978.
• 10: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 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.)
• 12: H. T. Kung , C. H. Papadimitriou, An optimality theory of concurrency control for databases, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582114]
• 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.
• 14: LAMPORT, L. Proving the correctness of multiprocess programs. IEEE Trans. Softw. Eng. SE- 3, 2 (March I977), 125-143.
• 15: Leslie Lamport, Concurrent reading and writing, Communications of the ACM, v.20 n.11, p.806-811, Nov. 1977 [doi>10.1145/359863.359878]
• 16: Philip L. Lehman , s. Bing Yao, Efficient locking for concurrent operations on B-trees, ACM Transactions on Database Systems (TODS), v.6 n.4, p.650-670, Dec. 1981 [doi>10.1145/319628.319663]
• 17: MANNA, Z., AND WALDINGER, R. The logic of computer programming. IEEE Trans. Softw. Eng. SE-4, 3 (May 1978), 199-229.
• 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.
• 19: Susan Speer Owicki, Axiomatic proof techniques for parallel programs., 1975
• 20: Daniel R. Ries , Michael Stonebraker, Effects of locking granularity in a database management system, ACM Transactions on Database Systems (TODS), v.2 n.3, p.233-246, Sept. 1977 [doi>10.1145/320557.320566]
• 21: SAMAra, B. B-trees in a system with multiple users. Inf. Process. Lett. 5, 4 (Oct. 1976), 107-112.
• 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.
• 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.
• 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.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Concurrency

General Terms:
Algorithms, Design

Keywords:
binary search trees, concurrency controls, concurrent algorithm, consistency, correctness, data structures, databases, locking protocols