Patent ID: 8200633
Filing Date: 2012-06-12
Classification: G06F

Abstract:
1. A method for reorganizing a source index tree of a database table resulting in a target index tree of the database table, the method comprising: performing a backup of the source index tree from respective source storage locations, wherein the source index tree comprises source leaf pages and source non-leaf pages, wherein the source leaf pages comprise index records specifying respective index keys and respective table row identifiers of the database table, a source logical order defined by a sequence of the respective index keys of the index records, and a source physical order defined by a sequence of the respective source storage locations, wherein the source physical order of the source leaf pages being possibly different from the source logical order of the source leaf pages, and wherein performing the backup of the source index tree from the source storage locations comprises: determining a sequence of the source storage locations according to the source logical order of the source leaf pages, reading the source leaf pages from the source storage locations according to the determined sequence of the source storage locations, constructing target leaf pages of the target index tree, the target leaf pages having copies of the index records and a target logical order defined by the sequence of the index keys of the copies of the index records; and performing a restore of the target index tree at target storage locations, wherein performing the restore of the target index tree at target storage locations comprises: writing the constructed target leaf pages to the respective target storage locations defining a target physical order of the target leaf pages, the target physical order corresponding to the target logical order of the target leaf pages, constructing target non-leaf pages of the target index tree based on the distribution of the index keys among the constructed leaf pages, and writing the constructed target non-leaf pages to the respective target storage locations, wherein the method further comprises: creating index change records describing changes of the source index tree while performing the backup of the source index tree, each of the index change records specifying a respective timestamp, a respective change operation and a respective changed index record associated with the change operation being an insert or delete operation; sorting the created index change records in the order of the respective index keys identifying the changed index records, in the order of respective timestamps; merging the index records from the source leaf pages and the sorted index change records by performing the respective change operations, resulting in merged index records, and thereby maintaining a sequence of the respective index keys of the merged index records; and inserting the merged index records to the respective constructed target leaf pages.