Information Technology Reference
In-Depth Information
and balanced, the undo pass of
ARIES
can be safely executed on it. The correctness
of the undo-insert and undo-delete algorithms in Sect.
4.3
, the B-tree traversal
algorithms in Chap.
7
, and the structure-modification algorithms in this chapter
then imply that the resulting B-tree b
00
is consistent and balanced and indexes the
database produced by the completed history.
t
8.6
Bottom-Up Structure Modifications
The traditional approach to B-tree structure modifications is to perform the modifi-
cations bottom-up, so that the leaf page is modified first and then the modification
is propagated up the insertion or deletion path, level by level, as high as needed.
The advantage of this approach over our top-down approach is that no unnecessary
modifications occur. Note that in the top-down approach, even when the saved path
is utilized, we may unnecessarily split a page on the insertion path. This may happen
when the page does not have room for a record with a maximum-length key or when
other transactions delete on the same path between the optimistic and pessimistic
traversals (see Problem
8.6
).
However, bottom-up modifications have a major disadvantage. When pages
at more than one level have to be split or merged, the B-tree cannot be kept
in a consistent state between the modifications. Therefore, the entire sequence
of structure modifications needed on an insertion or a deletion path must be
made a single atomic unit of work. The usual approach is to log the structure
modifications with several redo-undo log records written for a special system-
generated
structure-modification transaction
that commits as soon as the entire
sequence of modifications is completed.
In recovery from a process failure or a system crash, it may happen that for
a structure-modification transaction that encompasses several modifications and is
logged with several log records, only some but not all of those log records are
found on the log disk. Such a structure modification must be rolled back As the
modifications are all physical operations, only physical undo is possible.
Example 8.15
Consider executing the insert action I Œ16;
v
0
on the database of
Fig.
7.1
when pages are split in bottom-up order, in contrast to the top-down order
used in Example
8.7
. As the index record pointing to the new sibling page created
in a split cannot be inserted into a full parent page, the insertion of the index record
must be made a separate modification, to be executed when the parent page has been
split. Thus, we split p
6
creating p
0
6
, then split p
3
creating p
0
3
, then insert the index
record .12; p
0
6
/ into page p
3
, then increase the height of the tree, and finally insert
the index record .65; p
0
3
/ into page p
0
1
. The following log records are written:
n
1
Wh
S;
begin-smo
i
,
n
2
Wh
S;
page-split
;p
6
;12;p
0
6
;s
3
;V
4
;1;n
1
i
,
n
3
Wh
S;
page-split
;p
3
; 25; p
0
3
;s
2
;V
3
;2;n
2
i
,
n
4
Wh
S;
insert-index-record
;p
3
;12;p
0
6
;n
3
i
,
