Information Technology Reference
In-Depth Information
latched and page p
0
D
p
7
read-latched, so that the next key, 17, can be X-locked for
short duration and the tuple .16;
v
0
/ can be inserted into p
0
6
.
t
Similarly, when in the procedure
find-page-for-delete
(Algorithm
7.9
) it is found
that the page containing the tuple .x;
v
/ to be deleted is about to underflow, that
is, would underflow by the deletion, the procedure call
start-for-page-merges
.p; x/
(Algorithm
8.8
) is issued so as to determine the starting page for page merges, that
is, the highest-level page p on the path down to the page covering x that needs a
structure modification (tree-height decrease or page merge or records redistribution)
in order to accommodate the deletion. That page must satisfy condition (1) above
and the following condition:
3. The number of records in page p is greater than the required minimum number
of records in a leaf page (if p is a leaf page) or that in a non-leaf page (if p is a
non-leaf page), unless p is the root page.
Once the starting page p has been determined, a sequence of page merges or
records redistributes, possibly preceded by a tree-height decrease, is performed top-
down along the path down to the page that currently holds the tuple .x;
v
/.Thisis
done by the procedure call
top-down-page-merges
.p; x/ (Algorithm
8.9
), where p
is the page-id of the write-latched starting page. The call determines again the path
down to the leaf page containing .x;
v
/, performs the structure modifications needed
level-by-level, and saves the path.
Algorithm 8.8
Procedure
start-for-page-merges
.p; x/
i the least index for which either
path
Œi :
page-id
is the page-id of the root or
path
Œi :
#records
is greater than the required minimum number of records in a non-root leaf page (if i D 1)orin
a non-leaf page (if i>1)
p
path
Œi :
page-id
fix-and-write-latch
.p/
while
page p is not the root
do
if
P
AGE
-LSN.p/ D
path
Œi :
page-lsn
and
path
Œi :
low-key
x<
path
Œi :
high-key
or
p is a
B-tree page with x
1
x x
2
for the keys x
1
and x
2
of some records in page p
then
if
the number of records in page p is greater than the required minimum number of records
in a non-root leaf page (if p is a leaf page) or that in a non-leaf page (if p is a non-leaf
page)
then
exit the
while
loop
end if
end if
unlatch-and-unfix
.p/
i i C1
p
path
Œi :
page-id
fix-and-write-latch
.p/
end while
if
page p is the root
then
save-root
.p/
end if
