Patent ID: 6591269
Filing Date: 2003-07-08
Classification: G06F

Abstract:
In a database system, said database system storing a plurality of data records as a data table having an index, said index including a B-Tree comprising a multi-level structure having leaf-level and nonleaf-level pages for facilitating access to the database table according to a particular key order, a method for rebuilding the index comprising:(a) receiving a request for online rebuilding of the index; and (b) rebuilding the index online by: (i) allocating new pages for storing index pages; (ii) rebuilding the leaf-level pages by copying information, in key order, from the leaf pages to the new pages; (iii) propagating the rebuilding of the leaf-level pages to higher nonleaf-level pages of the index; and (iv) reorganizing the nonleaf-level pages that are at a level directly above the leaf-level pages while propagating the rebuilding of the leaf-level pages, so as to eliminate a separate pass for reorganizing pages of that level.