A Concurrent Blink-Tree Algorithm Using a Cooperative Locking Protocol

  • Sung-Chae Lim
  • Joonseon Ahn
  • Myoung Ho Kim
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2712)


We present a new concurrent Blink-tree algorithm that provides a concurrent tree restructuring mechanism for handling underflow nodes as well as overflow nodes. Our algorithm does not require any lock for downward searching and preserves bottom-up tree restructuring without deadlock. To this end, we develop a new locking mechanism for inserters and deleters and a node update rule that preserves the semantical tree consistency during tree restructuring. Our analytical experiment shows that the overhead of additional disk I/O is acceptable.


Index Entry Parent Node Concurrency Control Search Operation Sibling Node 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    D. Comer: The Ubiquitous B-tree. ACM Computing Surveys, 11(2) (1979) 121–137zbMATHCrossRefGoogle Scholar
  2. 2.
    Bayer, R. and Schkolnick, M.: Concurrency of Operations on B-Trees. Acta Informatica 9 (1977) 1–21zbMATHCrossRefMathSciNetGoogle Scholar
  3. 3.
    Philip L. Lehman and S. Bing Yao: Efficient Locking for Concurrent Operations. ACM Transactions on Database Systems 6(4) (1981) 650–670zbMATHCrossRefGoogle Scholar
  4. 4.
    Udi Manber and Richard E. Ladner: Concurrency Control In a Dynamic Search Structure. ACM Transactions on Database Systems 9(3) (1984) 439–455CrossRefMathSciNetGoogle Scholar
  5. 5.
    Yat-Sang Kwong and Derick Wood: A New Method for Concurrency in B-Trees. IEEE Transactions on Software Engineering 8(3) (1982) 211–222CrossRefGoogle Scholar
  6. 6.
    Yehoshua Sagiv: Concurrent Operations on B*-Tree with Overtaking. Journal of Computer and System Science 33(2) (1986) 275–296zbMATHCrossRefMathSciNetGoogle Scholar
  7. 7.
    Shasha, D. and Goodman, N.: Concurrent Search Structure Algorithms. ACM Transactions on Database Systems 13(1) (1988) 53–90zbMATHCrossRefGoogle Scholar
  8. 8.
    C. Mohan: ARIES:IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging. ACM SIGMOD 21 (1992) 371–380CrossRefGoogle Scholar
  9. 9.
    Ragaa Ishak: Semantically Consistent Schedules for Efficient and Concurrent B-Tree Restructuring. International Conference on Data Engineering (1992) 184–191Google Scholar
  10. 10.
    Chendong Zou and Betty Salzberg: On-line Reorganization of Sparsely-populated B+-trees. ACM SIGMOD 25 (1996) 115–124CrossRefGoogle Scholar
  11. 11.
    Jan Jannink: Implementing Deletion in B+-Trees. ACM SIGMOD 24 (1995) 33-38Google Scholar
  12. 12.
    Gray, J. and Reuter, A.: Transaction Processing: Concepts and Techniques. Reading Mass (1993) 449–490. Morgan Kaufmann Pub.Google Scholar
  13. 13.
    Johnson, T. and Shasha, D.: The Performance of Current B-Tree Algorithms. ACM Transactions on Database Systems, 18(1) (1993) 51–101CrossRefMathSciNetGoogle Scholar
  14. 14.
    V. Shrinivasan and Michael J. Carey: Performance of B+ Tree Concurrency Control Algorithms. VLDB Journal 2 (1993) 361–406CrossRefGoogle Scholar
  15. 15.
    Johnson, T. and Shasha, D.: The Performance of Current B-Tree Algorithms. ACM Transactions on Database Systems 18(1) (1993) 51–101CrossRefMathSciNetGoogle Scholar
  16. 16.
    Jayant R. Haritsa and S. Seshadri: Real-Time Index Concurrency Control. SIGMOD Record 25(1) (1996) 13–17CrossRefGoogle Scholar
  17. 17.
    Theodore Johnson and Dennis Shasha: B-trees with Inserts and Deletes: Why Free-at-Empty is Better than Merge-at-Half. Journal of Computer and System Science 40 (1993) 45–76CrossRefMathSciNetGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2003

Authors and Affiliations

  • Sung-Chae Lim
    • 1
  • Joonseon Ahn
    • 2
  • Myoung Ho Kim
    • 3
  1. 1.WST Lab.Korea Wisenut Inc.SeoulKorea
  2. 2.Hankuk Aviation UniversityKoyang, KyounggidoKorea
  3. 3.Korea Advanced Institute of Science and Technology 373-1TaejonKorea

Personalised recommendations