Technical Reports


Click here for full text: PDF

A survey of B-tree locking techniques

Graefe, Goetz
HP Laboratories


Keyword(s): storage systems, databases, B-tree, indexes, concurrency control, locking

Abstract: B-trees have been ubiquitous in database management systems for several decades, and they are used in other storage systems as well. Their basic structure and basic operations are well and widely understood including search, insertion, and deletion. Concurrency control of operations in B-trees, however, is perceived as a difficult subject with many subtleties and special cases. The purpose of this survey is to clarify, simplify, and structure the topic of concurrency control in B-trees by dividing it into two sub-topics and exploring each of them in depth.

17 Pages

Additional Publication Information: To be published in ACM Transactions on Database Systems (TODS), Volume 35, Issue 2, 2010.

External Posting Date: January 21, 2010 [Fulltext]. Approved for External Publication
Internal Posting Date: January 21, 2010 [Fulltext]

Back to Index