Foundations and Trends® in Databases > Vol 3 > Issue 4

Modern B-Tree Techniques

Goetz Graefe, Hewlett-Packard Laboratories, USA, goetz.graefe@hp.com
 
Suggested Citation
Goetz Graefe (2011), "Modern B-Tree Techniques", Foundations and TrendsĀ® in Databases: Vol. 3: No. 4, pp 203-402. http://dx.doi.org/10.1561/1900000028

Published: 20 Aug 2011
© 2011 G. Graefe
 
Subjects
Query Processing and Optimization,  Approximate and Interactive Query Processing,  Adaptive Query Processing
 

Free Preview:

Article Help

Share

Download article
In this article:
1. Introduction
2. Basic Techniques
3. Data Structures and Algorithms
4. Transactional Techniques
5. Query Processing
6. B-tree Utilities
7. Advanced Key Structures
8. Summary and Conclusions
Acknowledgments
References

Abstract

Invented about 40 years ago and called ubiquitous less than 10 years later, B-tree indexes have been used in a wide variety of computing systems from handheld devices to mainframes and server farms. Over the years, many techniques have been added to the basic design in order to improve efficiency or to add functionality. Examples include separation of updates to structure or contents, utility operations such as non-logged yet transactional index creation, and robust query processing such as graceful degradation during index-to-index navigation.

This survey reviews the basics of B-trees and of B-tree indexes in databases, transactional techniques and query processing techniques related to B-trees, B-tree utilities essential for database operations, and many optimizations and improvements. It is intended both as a survey and as a reference, enabling researchers to compare index innovations with advanced B-tree techniques and enabling professionals to select features, functions, and tradeoffs most appropriate for their data management challenges.

DOI:10.1561/1900000028
ISBN: 978-1-60198-482-1
208 pp. $99.00
Buy book
 
ISBN: 978-1-60198-483-8
208 pp. $150.00
Buy E-book
Table of contents:
1. Introduction
2. Basic Techniques
3. Data Structures and Algorithms
4. Transactional Techniques
5. Query Processing
6. B-tree Utilities
7. Advanced Key Structures
8. Summary and Conclusions
Acknowledgements
References

Modern B-Tree Techniques

Invented about 40 years ago and called ubiquitous less than 10 years later, B-tree indexes have been used in a wide variety of computing systems from handheld devices to mainframes and server farms. Over the years, many techniques have been added to the basic design in order to improve efficiency or to add functionality. Examples include separation of updates to structure or contents, utility operations such as non-logged yet transactional index creation, and robust query processing such as graceful degradation during index-to-index navigation.

Modern B-Tree Techniques reviews the basics of B-trees and of B-tree indexes in databases, transactional techniques and query processing techniques related to B-trees, B-tree utilities essential for database operations, and many optimizations and improvements. It is intended both as a tutorial and as a reference, enabling researchers to compare index innovations with advanced B-tree techniques and enabling professionals to select features, functions, and tradeoffs most appropriate for their data management challenges.

 
DBS-028