Gesellschaft für Informatik e.V.

Lecture Notes in Informatics

Datenbanksysteme in Business, Technologie und Web (BTW) P-144, 27-46 (2009).

Gesellschaft für Informatik, Bonn

Copyright © Gesellschaft für Informatik, Bonn


Efficient verification of B-treeintegrity

G. Graefe and R. Stonecipher


The integrity of B-tree structures can become compromised for many reasons. Since these inconsistencies manifest themselves in unpredictable ways, all commercial database management systems include mechanisms to verify the integrity and trustworthiness of an individual index and of a set of related indexes, and all vendors recommend index verification as part of regular database maintenance. This paper introduces algorithms for B-tree validation, reviews the algorithms' strengths and weaknesses, and proposes a simple yet effective improvement for key verification across multiple B-tree levels. The performance is such that B-tree verification can become part of scans or backups. Our experimental comparisons include algorithm performance and scalability measured using a shipping product.

Full Text: PDF

Gesellschaft für Informatik, Bonn
ISBN 978-3-88579-238-3

Last changed 04.10.2013 18:20:31