Title

Efficient Locking for Concurrent Operations on B-Trees

Overview

As we know, B-trees and their variants are very useful in database systems. However, I do not understand the performance of these datastructures very well. In this project, I will compare the naive approach and some other concurrent solutions, and analyze their properties. I will focus on the B-Link algorithm.

Paper

Philip L. Lehman and S. Bing Yao. Efficient Locking for Concurrent Operations on B-Trees ACM Transactions on Database Systems, 6(4): 650-670, December 1981.

Additional reading material

  1. Mark Allen Weiss. Data Structures and Algorithm Analysis in C. Addison-Wesley. 1997.
  2. Duane A. Bailey. Data Structures in Java for the Principled Programmer. McGraw-Hill. 1999.
  3. Dennis Shasha and Nathan Goodman. Concurrent Search Structure Algorithms. ACM Transactions on Database Systems, 13(1): 53-90, March 1988.
  4. V. Srinivasan and M. Carey. Performance of B-Tree Concurrency Control Algorithms. In Proceedings of the 1991 ACM SIGMOD International Conference on Management of Data, Denver, Colorado, May 1991. ACM. SIGMOD Record, 20(2): 416-425, June 1991.
  5. Alexandros Biliris. Operation Specific Locking in B-Trees. In Proceedings of the Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 159-169, San Diego, California, March 1987. ACM

Implementation details

  1. Implement the naive approach in Java.
  2. Implement the B-Link algorithm proposed by authors in Java.
  3. (Optional) Implement Bayer-Schkolnick algorithm in Java.