Information Technology Reference
In-Depth Information
Given a key range Œ
z
;
z
2
, the call
find-page-for-bulk-delete
.p; p
0
;
z
;
z
2
/ traverses
the B-tree and determines the leaf page p that covers the key
z
and, if
z
2
is greater
than the greatest key in p, the page p
0
next to p, write-latching p and read-latching
p
0
(if any). The call also arranges, with appropriate structure modifications, that the
page p will not underflow when a tuple is deleted. The set S of tuples to be deleted
from p at this time contains a maximum number of tuples in the range Œ
z
;
z
2
that
can be deleted without causing the page to underflow. The call
delete-bulk-from-
page
.T;p;S/(Algorithm
10.5
) is used to delete the tuples in S from page p and to
log the deletions with the redo-undo log records (
3.10
).
If tuples remain in page p that qualify for deletion, then in the next iteration
of the
while
loop in Algorithm
10.3
,
find-page-for-bulk-delete
.p; p
0
;
z
;
z
2
/ is called
with
z
being the key of the first not-yet-deleted tuple in page p. As the page now is
about to underflow, the call performs page merges or records redistributes, possibly
preceded by a tree-height decrease, so that the page holding the tuple with key
z
will
tolerate the deletion of more tuples.
Algorithm 10.3
Procedure
bulk-delete
.T; s
X
;s
XV
/
sort the key ranges in s
X
in ascending key order
s
XV
;
for
all ranges Œ
z
1
;
z
2
2 s
X
do
k maxfi j 0 i m; g
i
.
z
1
/ D g
i
.
z
2
/g
for
i D 0 to k 1
do
lock
.T; g
i
.
z
1
/; IX; short-duration/
end for
lock
.T; g
k
.
z
1
/; X; short-duration/
z
z
1
while
z
z
2
do
find-page-for-bulk-delete
.p; p
0
;
z
;
z
2
/
S
0
the tuples in page p with keys in Œ
z
;
z
2
, sorted in ascending key order
S the longest prefix of S
0
that can be deleted without page p underflowing
y the least key in
keys
.p/[
keys
.p
0
/[f1ggreater than the keys in S
if
y>
z
2
then
for
i D 0 to m1
do
conditionally-lock
.T; g
i
.y/; IX; commit-duration/
end for
conditionally-lock
.T; y; X; commit-duration/
if
some of the requested locks were not granted
then
unlatch-and-unfix
.p; p
0
/
for
i D 0 to m1
do
lock
.T; g
i
.y/; IX; commit-duration/
end for
lock
.T; y; X; commit-duration/
continue with the
while
loop
end if
end if
delete-bulk-from-page
.T;p;S/
unlatch-and-unfix
.p; p
0
/
s
XV
s
XV
[S
z
y
end while
release the short-duration locks
end for
