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
- Mark Allen Weiss.
Data Structures and Algorithm Analysis in C.
Addison-Wesley. 1997.
- Duane A. Bailey.
Data Structures in Java for the Principled Programmer.
McGraw-Hill. 1999.
- Dennis Shasha and Nathan Goodman.
Concurrent Search Structure Algorithms.
ACM Transactions on Database Systems, 13(1): 53-90, March 1988.
- 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.
- 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
- Implement the naive approach in Java.
- Implement the B-Link algorithm proposed by authors in Java.
- (Optional) Implement Bayer-Schkolnick algorithm in Java.