Information Technology Reference
In-Depth Information
Otherwise, we must unlatch pages p and p
0
, unlock key y, and repeat the
search for the pages and the next key by performing again the call
find-page-for-
insert
.p; p
0
;x;
v
;y/, locking the found key y conditionally, and so on.
The delete action DŒx;
v
is implemented analogously by the procedure
delete
.T; x;
v
/ (Algorithm
6.8
). First, the key x is unconditionally X-locked for
short duration. Then the call
find-page-for-delete
.p; p
0
;x;y/ is used to locate and
write-latch the data page p that covers key x and to locate and read-latch the data
page p
0
that contains the key y next to x if that key is not found in page p (and
high-
key
.p/ <
1
). Again, if p
6D
p
0
, the pages p and p
0
cover two successive subranges
of the key space. The call also ensures (by appropriate structure modifications)
that page p will not underflow by the deletion of a single tuple (if the physical
database structure requires that each data page should have at least a specified
minimum number of tuples). In Sect.
7.5
we give an implementation for the call
find-page-for-delete
.p; p
0
;x;y/in the case of a sparse B-tree.
Algorithm 6.8
Procedure
delete
.T; x;
v
/
lock
.T; x; X; short-duration/
while
true
do
find-page-for-delete
.p; p
0
;x;y/
conditionally-lock
.T; y; X; commit-duration/
if
the lock on y was granted
then
exit the
while
loop
else
m P
AGE
-LSN.p/
m
0
P
AGE
-LSN.p
0
/
unlatch-and-unfix
.p; p
0
/
lock
.T; y; X; commit-duration/
fix-and-write/read-latch
.p; p
0
/
if
P
AGE
-LSN.p/ D m
and
P
AGE
-LSN.p
0
/ D m
0
or
p D p
0
and
p is a data page with
x
1
x x
2
where x
1
is the least and x
2
the greatest key in page p
and
p does not
underflow by the deletion of a tuple
and
y is the least key in p greater than x
then
exit the
while
loop
else
unlatch-and-unfix
.p; p
0
/
unlock
.T; y; X; commit-duration/
end if
end if
end while
if
page p does not contain a tuple with key x
then
unlatch-and-unfix
.p; p
0
/
return with error
else
delete-from-page
.T;p;x/
unlatch-and-unfix
.p; p
0
/
unlock
.T; x; X; short-duration/
end if