Information Technology Reference
In-Depth Information
Algorithm 11.5
Side-file processing
T new transaction identifier
log
.n;h
begin-process-side-file-with
;Ti/
for
all pages q
0
in the side file of the index
do
fix-and-read-latch
.q
0
/
for
all records t in page q
0
do
if
t is of the form .
ix-I
;y;x;p/
then
insert-index-record
.T;y;x;p/
else if
t is of the form .
ix-D
;y;x;p/
then
delete-index-record
.T;y;x;p/
else if
t is of the form .
ix-I
1
;y;x;p/
then
delete-index-record
.T;y;x;p/
else if
t is of the form .
ix-D
1
;y;x;p/
then
insert-index-record
.T;y;x;p/
end if
end for
if
q
0
is the last page of the side file
then
commit
.T /
set the index as available in the system catalog
unlatch-and-unfix
.q
0
/
deallocate the side file
else
unlatch-and-unfix
.q
0
/
end if
end for
11.7
Restoration of Clustering
An index structure such as the B-tree maintains its balance under insertions, updates,
and deletions, so that the search-path length for a single key is logarithmic in the
number of indexed tuples (as stated in Lemma
7.3
). However, as new pages are
allocated in page splits and emptied pages are deallocated in page merges, the
structure gradually becomes
physically fragmented
, so that the B-tree pages are
scattered all over the disk, even if all the pages were initially located close to each
other in consecutive disk blocks of adjacent cylinders.
In traditional
offline reorganization
of a primary index structure (sparse B-tree),
the database system administrator runs periodically a system transaction that S-
locks the relation, thus quiescing all updates by transactions; traverses the entire
structure in key order and builds a new structure in a newly allocated disk area,
thus removing physical fragmentation; and finally upgrades the S lock on the
relation to an X lock, write-latches the system-catalog page containing the index
information, and substitutes the address of the new structure for the old one. During
the reorganization, which may take a long time, other transactions cannot update the
relation.
Online reorganization
attempts to circumvent the drawback of offline reor-
ganization. Other transactions are allowed to access the old structure when the
reorganization is in progress; when the new structure is ready, it is atomically
