Information Technology Reference
In-Depth Information
a
b
Fig. 8.2
Page merges are needed to accommodate the deletion DŒx;
v
because the page contain-
ing the tuple .x;
v
/ to be deleted is about to underflow. (
a
) Before deletion (
b
) After deletion
Similarly, in the case of a deletion, if it is found that the leaf page containing the
tuple .x;
v
/ to be deleted would underflow by the deletion, the calls
start-for-page-merges
.p; x/
top-down-page-merges
.p; x/
are performed in order to make the leaf page not about to underflow. 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 merge, records redistribute, or
tree-height decrease). The latter call then performs the merges, in top-down order,
starting at the child of page p on the path.
Example 8.2
In the case of Fig.
8.2
a, the call
start-for-page-merges
.p; x/ returns
with p
D
p
2
, because pages p
3
and p
4
have to be merged with their sibling pages
p
0
3
and p
0
4
, respectively. Figure
8.2
b shows the situation after calling
top-down-page-
merges
.p
2
;x;
v
/ and deleting the tuple .x;
v
/ from page p
4
.First,pagesp
3
and p
0
3
were merged by moving the records in p
0
3
to p
3
, detaching p
0
3
as a child p
2
,and
deallocating p
0
3
. Second, pages p
4
and p
0
4
were merged by moving the tuples in p
0
4
to p
4
, detaching p
0
4
as a child of p
3
, and deallocating p
0
4
. Third, the tuple .x;
v
/ was
deleted from page p
4
that now does not underflow by the deletion.
t
The page splits and merges are thus performed in a top-down order, each
retaining the consistency and balance of the B-tree. Each split or merge can thus
be made a redo-only atomic unit of work, logging it with a single redo-only log
record, following the principle discussed in Sects.
2.8
,
3.5
,and
4.11
. In the case of
Example
8.1
, two redo-only page-split log records are generated, and in the case of
Example
8.2
, two redo-only page-merge log records are generated.
Each of the five B-tree structure modifications to be defined (tree-height increase,
page split, tree-height decrease, page merge, and records redistribute) modifies three
