Information Technology Reference
In-Depth Information
page-id page-lsn low-key high-key max-key #records space-left
1: p
4
:::
1
5 3 2 4 records
2: p
2
:::
1
8 5 2 4 records
3: p
1
:::
1 1
99 6 0
(Fig.
8.9
a). Because page p
4
would underflow by the deletion of the tuple, the write
latch on the page is released, and the call
start-for-page-merges
.p; 3/ is performed.
As page p
4
and its parent page p
2
are about to underflow, but the grandparent p
1
is
not, the call returns with p
D
p
1
.
Next the call
top-down-page-merges
.p; 3/ with p
D
p
1
is performed. Here the
records in page p
2
and its sibling page p
3
are redistributed by the call
records-
redistribute
.p
1
;p
2
;x
0
;p
3
/ that returns x
0
D
20,andthepagep
5
is merged into
its sibling page p
4
by the call
page-merge
.p
2
;p
4
;x
0
;p
5
/ that returns x
0
D
5.The
following log records are written:
n
1
Wh
records-redistribute
;p
1
;p
2
; 20; p
3
;V
1
;
i
,
n
2
Wh
page-merge
;p
2
;p
4
;5;p
5
;V
2
i
,
where the sets of records moved are:
V
1
Df
.8; p
6
/; .17; p
7
/
g
, from page p
3
to page p
2
(direction
),
V
2
Df
.5; : : :/; .6; : : :/; .7; : : :/
g
, from page p
5
to page p
4
(Fig.
8.9
b). The call
top-down-page-merges
.p; 3/ saves the path p
1
!
p
2
!
p
4
and returns with p
D
p
4
. The key, 5, next to 3 now resides in the same page; so
it can be X-locked for commit durationandthetuplewithkey3bedeletedfrom
page p
4
.
t
Fig. 8.9
Delete action DŒ3;
v
0
on the B-tree of Fig.
7.1
triggers a redistribution of records between
pages p
2
and p
3
and a merge of pages p
4
and p
5
