Information Technology Reference
In-Depth Information
The index-construction algorithm in this chapter has been adapted from that
presented by Mohan and Narang [
1992
] for their method named “bottom-up index
build with side file (algorithm
SF
).” Mohan and Narang [
1992
] suggest using a
restartable merge-sort algorithm to merge the sorted runs created from tuples pulled
from the priority queue, so that the B-tree can be constructed bottom-up, filling
each page with a prespecified amount of records from the single sorted sequence of
records.
Sockut and Iyer [
1996
] survey the different methods for the restoration of
clustering in
DB2
databases. Sockut et al. [
1997
] present an algorithm for online
reorganization that scans the data from the old structure and stores it into a new
clustered structure, removing overflow and distributing free space evenly, and finally
brings the new structure up-to-date by capturing from the log transactions' updates
missed by the scan. The algorithm outlined in Sect.
11.7
is an adaption of one of
the methods of Sockut and Iyer [
1996
]. Sockut and Iyer [
2009
] present an extensive
survey of methods for online reorganization of databases. Salzberg and Dimock
[
1992
] address the problem of updating the references to tuples relocated in online
reorganization. Zou and Salzberg [
1996a
,
b
] give online algorithms for relocating
and compacting the pages of sparsely populated B-trees. Sun et al. [
2005
]present
an algorithm for online merging of two B-trees.
