Information Technology Reference
In-Depth Information
8.1
Top-Down Redo-Only Modifications
In Sects.
7.4
and
7.5
, when discussing B-tree traversals for insertions and deletions,
we presented the procedures
find-page-for-insert
.p; p
0
;x;
v
;y/ and
find-page-for-
delete
.p; p
0
;x;y/(Algorithms
7.8
and
7.9
) that locate the leaf page p covering key
x and the leaf page p
0
containing the next key y and also arrange that page p can
accommodate the insertion or deletion of the tuple with key x.
In the case of an insertion, if it is found that the leaf page covering key x does
not have room for the tuple .x;
v
/, the calls
start-for-page-splits
.p; x;
v
/
top-down-page-splits
.p; x;
v
/
are performed in order to make room for the tuple. The former call returns the page-
id p of the highest-level page on the root-to-leaf path to the leaf page covering x that
needs modification (page split or tree-height increase). The latter call then performs
the splits, in top-down order, starting at the child of page p on the path.
Example 8.1
In the case of Fig.
8.1
a, the call
start-for-page-splits
.p; x;
v
/ returns
with p
D
p
2
, because pages p
3
and p
4
have to be split. Figure
8.1
bshowsthe
situation after calling
top-down-page-splits
.p
2
;x;
v
/ and inserting the tuple into
page p
4
.First,pagep
3
was split by allocating a new page p
0
3
, moving the upper
half of the records in p
3
to p
0
3
and linking p
0
3
as a child of p
2
. Second, page p
4
was
split by allocating a new page p
0
4
, moving the upper half of the records in p
4
to p
0
4
and linking p
0
4
as a child of p
3
. Third, the tuple .x;
v
/ was inserted into page p
4
that
now has room for the tuple.
t
a
b
Fig. 8.1
Page splits are needed to accommodate the insertion IŒx;
v
because the tuple .x;
v
/ does
not fit into the leaf page that covers key x.(
a
) Before insertion (
b
) After insertion
