Information Technology Reference
In-Depth Information
8.3
Tree-Height Decrease, Page Merge, and Records
Redistribute
In the
tree-height decrease
of a B-tree rooted at page p with two child pages, q
and q
0
, the index records pointing to these child pages are deleted from the parent
page p, the records from pages q and q
0
are moved to page p, the height of p is
decremented, and the pages q and q
0
are deallocated (Algorithm
8.3
), as illustrated
in Fig.
8.5
.
The tree-height-decrease modification is performed by the procedure call
tree-
height-decrease
.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 the output parameter x
0
(Algorithm
8.3
). The precondition for this modification is that the root page p has
exactly two child pages q and q
0
, all three pages are write-latched, and the records
in q and q
0
all fit into a single page. The modification is logged with the redo-only
log record
n
Wh
tree-height-decrease
;p;q;x
0
;q
0
;s;s
0
;V
i
;
(8.3)
where s and s
0
are the page-ids of the space-map pages that record the allocation
of q and q
0
,andV is the set of records moved to p.The
LSN
n of the log record is
stamped in the
P
AGE
-LSN
fields of pages p, q, q
0
, s,ands
0
. At the end, pages s, s
0
, q
and q
0
are unlatched, but page p remains write-latched.
In the
page merge
of sibling pages q and q
0
, one of which is about to underflow,
the index record pointing to q
0
is deleted from the parent page p, the records in page
q
0
are moved to page q, and page q
0
is deallocated (Algorithm
8.4
), as illustrated in
Fig.
8.6
.
Algorithm 8.3
Procedure
tree-height-decrease
.p;q;x
0
;q
0
/
delete the index records .1;q/and .x
0
;q
0
/ from the root page p
move the records in the child pages q and q
0
to the parent page p
V the set of records moved
format q and q
0
as free pages
height
.p/
height
.p/ 1
s the page-id of the space-map page that records q
s
0
the page-id of the space-map page that records q
0
fix-and-write-latch
.s; s
0
/
mark q as free in s and q
0
as free in s
0
log
.n;h
tree-height-decrease
;p;q;x
0
;q
0
;s;Vi/
P
AGE
-LSN.p/ P
AGE
-LSN.q/ P
AGE
-LSN.q
0
/ n
P
AGE
-LSN.s/ P
AGE
-LSN.s
0
/ n
unlatch-and-unfix
.s; s
0
/
unlatch-and-unfix
.q/
unlatch-and-unfix
.q
0
/
