Nagavamsi Ponnekanti
Abstract
In this paper we present an efficient method to do online rebuild of a B+-tree index. This method has been implemented in Sybase Adaptive Server Enterprise (ASE) Version 12.0. It provides high concurrency, does minimal amount of logging, has good performance and does not deadlock with other index operations. It copies the index rows to newly allocated pages in the key order so that good space utilization and clustering are achieved. The old pages are deallocated during the process. Our algorithm differs from the previously published online index rebuild algorithms in two ways. It rebuilds multiple leaf pages and then propagates the changes to higher levels. Also, while propagating the leaf level changes to higher levels, level 11 pages are reorganized, eliminating the need for a separate pass. Our performance study shows that our approach results in significant reduction in logging and CPU time. Also, our approach uses the same concurrency control mechanism as split and shrink operations, which made it attractive for implementation.
- Com79 Douglas Comer. The Ubiquitous B-Tree. Computing Surveys, Vol. 11, No. 2, June 1979. Google Scholar
Digital Library
- GR93 Jim Gray and Andreas Reuter. Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers, Inc., 1993. Google ScholarDigital Library
- LY81 Lehman, E L., and S. B. Yao. Efficient Locking for Concurrent operations on B-Trees. ACM TODS. Vol. 6, No. 4, pages 650-670, December 1981. Google ScholarDigital Library
- MF92 C. Mohan and Frank Levine. ARIES/IM: An Efficient and High Concurrency Index Management Method using Write-Ahead Logging. Proc. of ACM SIGMOD Conf, pages 371-380, 1992. Google ScholarDigital Library
- SBC97 Gary H. Sockut, Thomas A. Beavin and Chung-C. Chang: A Method for On-Line Reorganization of a Database. IBM Systems Journal. Vol. 36, No. 3, pages 411-436, 1997. Available at http://www.research.ibm.com/journal/sj/363/s o ckut. html Google ScholarDigital Library
- Smi90 Gary Smith. Online Reorganization of Key- Sequenced Tables and Files. Tandem Systems Review, October 1990.Google Scholar
- ZS96 Chendong Zou and Betty Salzberg. On-line Reorganization of Sparsely-populated B+ trees. Proc. ofACM SIG- MOD Conf, pages 115-124, 1996. Google ScholarDigital Library
Index Terms
- Online index rebuild
Recommendations
Resumable online index rebuild in SQL server
Azure SQL Database and the upcoming release of SQL Server enhance Online Index Rebuild to provide fault-tolerance and allow index rebuild operations to resume after a system failure or a user-initiated pause. SQL Server is the first commercial DBMS to ...
Online index rebuild
SIGMOD '00: Proceedings of the 2000 ACM SIGMOD international conference on Management of dataIn this paper we present an efficient method to do online rebuild of a B+-tree index. This method has been implemented in Sybase Adaptive Server Enterprise (ASE) Version 12.0. It provides high concurrency, does minimal amount of logging, has good ...
Szeged index, edge Szeged index, and semi-star trees
A semi-star tree is a star tree whose some edges may be replaced by paths of length more than one. In this paper we present some increasing and decreasing transformations for Szeged index of the semi-star trees. Then we introduce palm semi-star tree and ...
Comments