Information Technology Reference
In-Depth Information
a
b
Fig. 8.5
Decreasing the height of the B-tree. The pages q and q
0
are detached from the B-tree, their
records are moved to the root page p,andq and q
0
are deallocated. (
a
) Before height decrease (
b
)
After height decrease
a
b
Fig. 8.6
Merging a page. The records in page q
0
are moved to its sibling page q and page q
0
is
detached from the B-tree and deallocated. (
a
) Before merge (
b
)Aftermerge
The page-merge modification is performed by the procedure call
page-
merge
.p;q;x
0
;q
0
/, where the page-ids p, q,andq
0
are given as input parameters
and the least key in page q
0
is returned in x
0
(Algorithm
8.4
). The precondition
for this modification is that the parent page p and its child pages q and q
0
are
write-latched, q
0
is the next younger sibling of q, the records in q and q
0
all fit into
a single page, and the parent page p is not about to underflow. The modification is
logged with the redo-only log record
n
Wh
page-merge
;p;q;x
0
;q
0
;s
0
;V
0
i
;
(8.4)
where s
0
is the page-id of the space-map page that records the allocation of page q
0
and V
0
is the set of records that were moved from page q
0
to page q.The
LSN
n of
the log record is stamped in the
P
AGE
-LSN
fields of pages p, q, q
0
,ands
0
. At the end,
pages s
0
and q
0
are unlatched, but pages p and q remain write-latched.
