The B-tree and its variants are widely used for large index files in database systems. Since large databasses are typically shared among many different processes, there have been many works on improving the performance of B-trees when concurrent processes access B-trees. The previously proposed algorithms for B-tree concurrency control can be classified into two approaches, i.e. top-down and bottom-up approaches. Though both of them have their own advantages, they also have serious shortcomings. The top-down approach employs a simple and elegant idea, but suffers from low concurrency and large overhead. The bottom-up approach, on the other hand, does not support fullfeatured tree modification oprertions, i.e., deleter's B-tree reconstruction is not allowed. In this thesis, we propose a new B-tree concurrency control algorithm that overcomes problems in previous works. Our method achieves high concurrency with relatively low overhead, and also easily supports updater's B-tree reconstruction. We also show that the algorithm is correct and deadlock-free.
