Patent ID: 8626717

Claim:
A method utilizing at least a computer 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 the performing the backup of the source index tree from the respective source storage locations comprises: determining the sequence of the respective source storage locations according to the source logical order of the source leaf pages, reading the source leaf pages from the respective source storage locations according to the determined sequence of the respective source storage locations, wherein the reading the source leaf pages further comprises: receiving a read request for reading a specific source leaf page from a specific source storage location; reading a chunk of source leaf pages from the respective source storage locations in response to the read request, the specific source leaf page being a member of the chunk of source leaf pages; writing the read chunk of source leaf pages to cache storage locations according to the source physical order of the read source leaf pages; determining a sequence of the cache storage locations according to the source logical order of the source leaf pages; and reading the source leaf pages from the cache storage locations according to the determined sequence of the cache storage locations, and 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 a sequence of the index keys of the copies of the index records; and performing a restore of the target index tree at respective target storage locations, wherein performing the restore of the target index tree at the respective 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 distribution of the index keys among the constructed target leaf pages, and writing the constructed target non-leaf pages to the respective target storage locations.