Information Technology Reference
In-Depth Information
where s is the page-id of the space-map page that records the allocation of q and q
0
,
V is the set of records moved to q, V
0
is the set of records moved to q
0
,andh is the
height of pages q and q
0
.The
LSN
n of the log record is stamped in the
P
AGE
-LSN
fields of all the affected pages: p, q, q
0
,ands. At the end, page s is unlatched, but
pages p, q,andq
0
remain write-latched.
Algorithm 8.1
Procedure
tree-height-increase
.p;q;x
0
;q
0
/
s the page-id of some space-map page used to allocate pages for the B-tree
fix-and-write-latch
.s/
q the page-id of some page designated as free in s
mark q as allocated in s
q
0
the page-id of some page designated as free in s
mark q
0
as allocated in s
fix-and-write-latch
.q/
fix-and-write-latch
.q
0
/
format q and q
0
as empty B-tree pages
height
.q/
height
.q
0
/
height
.p/
move the lower half V of the records in page p to page q
move the upper half V
0
of the records in page p to page q
0
x
0
the least key of the records in page q
0
insert the index records .1;q/ and .x
0
;q
0
/ into page p
height
.p/
height
.p/ C1
log
.n;h
tree-height-increase
;p;q;x
0
;q
0
;s;V;V
0
;hi/,whereh D
height
.q/
P
AGE
-LSN.p/ P
AGE
-LSN.q/ P
AGE
-LSN.q
0
/ P
AGE
-LSN.s/ n
unlatch-and-unfix
.s/
In the
page split
of a full child page q of non-full parent page p, a page q
0
is allocated and write-latched and formatted as an empty B-tree page of the same
height as q, records from the upper half of page q starting from some key x
0
are
moved to page q
0
, and the index record .x
0
;q
0
/ is inserted into the parent page p,
thus making q
0
the next younger sibling of q (Algorithm
8.2
), as illustrated in
Fig.
8.4
.
The page-split modification is performed by the procedure call
page-
split
.p;q;x
0
;q
0
/, where the page-ids p and q are given as input parameters
a
b
Fig. 8.4
Splitting a full page. The records in page q are evenly distributed at key x
0
between q
and a new sibling page q
0
.(
a
) Before split (
b
) After split
