Operation specific locking in B-trees

ABSTRACT

B-trees have been used as an access and for both primary and secondary indexing for quite some time. This paper presents a deadlock free locking mechanism in which different processes make use of different lock types in order to reach the leaf nodes. The compatibility relations among locks on a node, do not exclusively depend on their type, but also on the node status and the number and kind of processes acting currently on the node. As a result, a number of insertion or deletion processes can operate concurrently on a node. The paper presents an appropriate recovery strategy in case of failure, and discusses the protocol modifications that are required so it can be used in other similar structures such as B+-trees, compressed B-trees, and R-trees for spatial searching.

REFERENCES

• Baye72: Bayer R and McCre~ght E Orgamzat~on and maintenance of large ordered indexes Acta In/ormatrca Vol 1 No 3 1972 pp 173-189
• Baye77: Bayer R and Schkolmck M Concurrency of Operat~ons on B-trees Acta lnformat~ca Vol 9 No 1 1977 pp 1-21
• Buck85: G. N. Buckley , A. Silberschatz, Beyond two-phase locking, Journal of the ACM (JACM), v.32 n.2, p.314-343, April 1985 [doi>10.1145/3149.3151]
• Bern81: Philip A. Bernstein , Nathan Goodman, Concurrency Control in Distributed Database Systems, ACM Computing Surveys (CSUR), v.13 n.2, p.185-221, June 1981 [doi>10.1145/356842.356846]
• Bern83: Bernstem P Goodman N and La~ M Analyzing Concurrency Control Algorithms when User and System Operations Differ IEEE Transactions on Software Engtneertng Vol SE-9 No 3 May 1983 pp 233-239
• Come79: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• Crok86: Albert Croker , David Maier, A Dynamic Tree-Locking Protocol, Proceedings of the Second International Conference on Data Engineering, p.49-56, February 05-07, 1986
• Elli80a: Elhs C Concurrent Search and Insertion m AVL Trees IEEE Transactions on Computers Vol C-29 No 9 September 1980 pp 811-817
• Elli80b: Elhs C Concurrent Search and insertion m 2-3 trees Acta Informat~ca Vol 14 No 1 1980 pp 63- 86
• Eswa76: 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]
• Ford84: Ray Ford , Jim Calhoun, Concurrency control mechanisms and the serializability of concurrent tree algorithms, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada [doi>10.1145/588011.588020]
• Garc83: Hector Garcia-Molina, Using semantic knowledge for transaction processing in a distributed database, ACM Transactions on Database Systems (TODS), v.8 n.2, p.186-213, June 1983 [doi>10.1145/319983.319985]
• Gray81: Jim Gray , Paul McJones , Mike Blasgen , Bruce Lindsay , Raymond Lorie , Tom Price , Franco Putzolu , Irving Traiger, The Recovery Manager of the System R Database Manager, ACM Computing Surveys (CSUR), v.13 n.2, p.223-242, June 1981 [doi>10.1145/356842.356847]
• Guib78: Gulbas C S Sedgewlck R A D~chromat~c Framework for Balanced Trees Proc of the 19th Annual Syrup Foundatwn Comp Science 1978 pp 8-21
• Gutt84: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• Haer83: Theo Haerder , Andreas Reuter, Principles of transaction-oriented database recovery, ACM Computing Surveys (CSUR), v.15 n.4, p.287-317, December 1983 [doi>10.1145/289.291]
• Kede83: Zvi M. Kedem , Abraham Silberschatz, Locking Protocols: From Exclusive to Shared Locks, Journal of the ACM (JACM), v.30 n.4, p.787-804, Oct. 1983 [doi>10.1145/2157.322406]
• Kers84: Kersten M L and Tebra H Application of an ()ptimmtlc Concurrency Control Method Softwarel~acttce and Expertence Eds John W tley and Sons ~ol 14 No 2 February 1984 pp 153-168
• Kung80: H. T. Kung , Philip L. Lehman, Concurrent manipulation of binary search trees, ACM Transactions on Database Systems (TODS), v.5 n.3, p.354-382, Sept. 1980 [doi>10.1145/320613.320619]
• Kwon82: Kwong h and Wood D A new method for concurrency m B-trees 1EEE Transacttons on Soft Engtneermg Vol 8 No 3 1982 pp 211-222
• Laus84: G Lausen, Integrated concurrency control in shared B-trees, Computing, v.33 n.1, p.13-26, 1984 [doi>10.1007/BF02243072]
• Lehm81: 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]
• Lync83: Nancy A. Lynch, Multilevel atomicity—a new correctness criterion for database concurrency control, ACM Transactions on Database Systems (TODS), v.8 n.4, p.484-502, Dec. 1983 [doi>10.1145/319996.319999]
• Manb84: Udi Manbar , Richard E. Ladner, Concurrency control in a dynamic search structure, ACM Transactions on Database Systems (TODS), v.9 n.3, p.439-455, Sept. 1984 [doi>10.1145/1270.318576]
• Mena81: Menasce D A and Landes O Dynamic Crash Recovery of Balanced Tress Proceedings o}' the Symposium on Relu2b,l~ty ~n D~str~buted Software and Database Systems Computer Science Press July 1981 pp 131- 137
• Mill78: Miller R and Snyder I Multiple access to B-trees Proceedings of the 12th Annual Conference tn Informatmn Science and Systems March 1978
• Mond85: Mond Y and Raz Y Concurrency Control m B+- Trees Databases Using Preparatory Operations Proc of the l lth lnt Conference on Very Large Databases Stockholm August 1985 pp 331-334
• Moss81: Moss J E B Nested Transactions An Approach to Reliable D~str~buted Computtng Ph D Thes~s Department of Electrical Engmeermg and Computer Science Massachusetts Ins~tute of Technology April 1981
• Moss86: J. Eliot B Moss , Nancy D. Griffeth , Marc H. Graham, Abstraction in recovery management, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.72-83, May 28-30, 1986, Washington, D.C., United States
• Reed78: Reed D Nanung and Synchron~zatwn ~n a Decentraltzed Comtmter System Ph D Thes~s Department of Electrical Engineering and Computer Science Massachusetts InsJtute of Technology June ,978
• Sama76: Samad~ B B-trees m a system w~th multiple users Information Processing letters Vol 5 No 4 1976 pp 107-112
• Sagi85: Yehoshua Sagiv, Concurrent operations on B-trees with overtaking, Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.28-37, March 25-27, 1985, Portland, Oregon, United States [doi>10.1145/325405.325409]
• Spec83: Alfred Z. Spector , Peter M. Schwarz, Transactions: a construct for reliable distributed computing, ACM SIGOPS Operating Systems Review, v.17 n.2, p.18-35, April 1983 [doi>10.1145/1041478.1041481]
• Spec85: Spector A Z Butcher J Darnels D S Duchamp D J Eppmger J L Freeman C E Heddaya A and Schwarz P Support for Dtstr~buted Transactions m the TABS Prototype 1EEE Transactwns on Software Engineering Vol SE-11 No 6 June 1985 pp 520-530
• Ston84: Michael Stonebraker , Lawrence A. Rowe, Database Portals: A New Application Program Interface, Proceedings of the 10th International Conference on Very Large Data Bases, p.3-13, August 27-31, 1984
• Weik86: Gerhard Weikum, A theoretical foundation of multi-level concurrency control, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.31-43, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15401]
• Yann79: Yannakakts M Papad~mitriou C H and Kung T H T Locking Policies Safety and Freedom from Deadlock Proc 20th IEEE Symposmm on Foundatwns o/Computer Science October 1979 pp 286-297

INDEX TERMS

Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Deadlock avoidance

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies

General Terms:
Design, Management, Standardization, Theory