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
 
Search WWH ::




Custom Search