Importance

Loading Importance Indicators...

Abstract

A database system providing an efficient methodology for performing an online rebuild of a B+-tree index is described. From a high-level perspective, the method operates by copying 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. This approach differs from the previously-published online index rebuild algorithms in two ways. First, it rebuilds multiple leaf pages and then propagates the changes to higher levels. Also, while propagating the leaf level changes to higher levels, level 1 pages (i.e., the level immediately above the leaf level) are reorganized, eliminating the need for a separate pass. The methodology provides high concurrency, does minimal amount of logging, has good performance and does not deadlock with other index operations. Performance study shows that the approach results in significant reduction in logging and CPU time. Also, the approach uses the same concurrency control mechanism as split and shrink operations, which made it attractive for implementation.

Loading the Abstract Image...

First Claim