TR-166: Efficient Concurrency Control Protocols for B-tree Indexes

Abstract

We address the problem of maintaining the consistency and integrity of a B-tree index under a number of independent asynchronous concurrently executing processes. Each process issues an insert, delete or look-up operation. We present a survey of some of the previous works in this area and propose two simple but efficient locking protocol for B-tree indexes. Update processes in our scheme make use of lock conversions. The protocols are deadlock and livelock free and each process ensures that the B-tree characteristics are maintained at all times.