Information Technology Reference
In-Depth Information
(Algorithm
8.2
). The precondition for this modification is that the parent page
p and its child page q are write-latched, page p has room for an index record with a
maximum-length key, and page q contains records enough so that distributing them
equally between two pages makes neither of them underflow. The modification is
logged with the redo-only log record
n
Wh
page-split
;p;q;x
0
;q
0
;s
0
;V
0
;h
i
;
(8.2)
where s
0
is the page-id of the space-map page that records the allocation of page q
0
,
V
0
is the set of records that were moved from page q to page 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
pages p, q, q
0
and s
0
. At the end, page s
0
is unlatched, but pages p, q,andq
0
remain
write-latched.
Algorithm 8.2
Procedure
page-split
.p;q;x
0
;q
0
/
s
0
the page-id of some space-map page used to allocate pages for the B-tree
fix-and-write-latch
.s
0
/
q
0
the page-id of some page designated as free in s
0
mark q
0
as allocated in s
0
fix-and-write-latch
.q
0
/
format q
0
as an empty B-tree page
height
.q
0
/
height
.q/
move the upper half V
0
of the records in page q to page q
0
x
0
the least key of the records in page q
0
insert the index record .x
0
;q
0
/ into the parent page p
log
.n;h
page-split
;p;q;x
0
;q
0
;s
0
;V
0
;hi/,whereh D
height
.q
0
/
P
AGE
-LSN.p/ P
AGE
-LSN.q/ P
AGE
-LSN.q
0
/ P
AGE
-LSN.s
0
/ n
unlatch-and-unfix
.s/
Example 8.3
In the case of Example
8.1
(Fig.
8.1
), the following log records are
written:
n
1
Wh
page-split
;p
2
;p
3
;
z
;p
0
3
;s
0
3
;V
0
3
;2
i
,
n
2
Wh
page-split
;p
3
;p
4
;y;p
0
4
;s
0
4
;V
0
4
;1
i
,
n
3
Wh
T; I; p
4
;x;
v
;n
0
i
,
where s
0
3
and s
0
4
are the page-ids of the space-map pages used to allocate the new
pages p
0
3
and p
0
4
, respectively V
0
3
is the set of index records moved from page p
3
to
page p
0
3
;
z
is the least key in p
0
3
; 2 is the height of p
3
and p
0
3
; V
0
4
is the set of tuples
moved from page p
4
to page p
0
4
; y is the least key in p
0
4
; 1 is the height of p
4
and p
0
4
,
and T is the identifier of the transaction that did the insertion and n
0
is its previous
U
NDO
-N
EXT
-LSN
. Observe that the B-tree is consistent and balanced after each of the
three logged operations, provided that it is so initially.
t
