Information Technology Reference
In-Depth Information
Algorithm
11.5
processes the records in the side file in their original appending
order and, for each record, performs on the index the update action represented
by the record. The processing is done in the name of a single transaction,
whose identifier is logged for restartability. Transactions may continue appending
to the side file while it is being scanned by the index constructor. For each
side-file record that represents an index-record insertion (i.e.,
ix-I
or
ix-D
1
),
an index-record insertion is performed, and for each side-file record that rep-
resents an index-record deletion (i.e.,
ix-D
or
ix-I
1
), an index-record deletion
is performed. Each such insertion or deletion is logged with a redo-undo log
record.
Algorithm 11.3
Procedure
index-bulk-insert
.T; f /
.y;x;p/ the first record in f
while
.y; x/ 6D .1;1/
do
find-page-for-index-bulk-insert
.p; y
0
;x
0
;p
0
;y;x;p/
S the records .y
00
;x
00
;p
00
/ in f with .y; x/ .y
00
;x
00
/<.y
0
;x
0
/ fitting in p
insert-index-bulk-into-page
.T;p;S/
unlatch-and-unfix
.p; p
0
/
if
the last record in f is in S
then
.y;x;p/ .1;1;0/
else
.y;x;p/ the first record in f not in S
end if
end while
Algorithm 11.4
Populating the index with sorted bulks f
2
F
log
.n;h
begin-populate-index
;Fi/
partition F into disjoint sets F
1
;:::;F
k
for some k
for
all i D 1;:::;k concurrently
do
for
all files f 2 F
i
do
T new transaction identifier
log
.n;hT; Bi/
index-bulk-insert
.T; f /
commit
.T /
log
.n;h
populated-index-with
;fi/
end for
end for
process the side file with Algorithm
11.5
log
.n;h
end-populate-index
;Fi/
