Information Technology Reference
In-Depth Information
Algorithm 7.9
Procedure
find-page-for-delete
.p; p
0
;x;y/
find-page-for-update
.p; p
0
;x;false/
while
true
do
if
page p would underflow by the deletion of a single tuple
then
unlatch-and-unfix
.p; p
0
/
start-for-page-merges
.p; x/
top-down-page-merges
.p; x/
end if
if
page p contains a key greater than x
then
y the least key greater than x in page p
p
0
p
exit the
while
loop
else if
path
Œ1:
page-id
D p and
path
Œ1:
page-lsn
D P
AGE
-LSN.p/ and
path
Œ1:
high-key
D1
then
y 1
p
0
p
exit the
while
loop
else
{pessimistic traversal}
unlatch-and-unfix
.p; p
0
/
find-page-for-update
.p; p
0
;x;true/
if
page p
0
contains a key greater than x
then
y the least key greater than x in page p
0
else
y 1
end if
if
page p will not underflow by the deletion of a single tuple
then
exit the
while
loop
end if
end if
end while
(a)
(b)
Fig. 7.9
The simple case of deletion DŒx;
v
. The leaf page containing .x;
v
/ does not underflow
by the deletion, and the tuple with the least key y greater than x resides in the same page. (
a
)
Before deletion (
b
) After deletion
