Technical Reports
HPL-2010-9
A survey of B-tree locking techniques
Graefe, Goetz
HP Laboratories
HPL-2010-9
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]