Information Technology Reference
In-Depth Information
write latch and three read latches held simultaneously occurs when page p is read-
latched, its child, the leaf page covering x is write-latched, and a cousin of p and its
child containing the key next to x are read-latched.
When the X lock on the next key is granted immediately, only one call of the
procedure
find-page-for-insert
from the procedure
insert
is performed. In
find-page-
for-insert
, the call
find-page-for-update
.p; p
0
;x;false/ is first performed. As the
saved path has its initial value, the root page is read-latched, and then the path down
to the leaf page covering key x is latch-coupled with read latches on the remaining
non-leaf pages and a write latch on the leaf page, making one write-latching and
h
1 read-latchings in all.
When the leaf page covering x has room for .x;
v
/, the procedures
start-for-page-
splits
and
top-down-page-merges
are not called from
find-page-for-insert
.However,
if the leaf page p covering x does not contain the key next to x (and
high-key
.p/ <
1
), then a call
find-page-for-update
.p; p
0
;x;true/ is performed. This call uses the
path saved from the call
find-page-for-update
.p; p
0
;x;false/. As we assumed that
no other updates or structure modifications occur simultaneously, the saved path is
valid and the starting page for the top-down traversal is thus determined correctly
by the first assignment statement in Algorithm
7.7
, so no climbing up the path
occurs.
In the worst case, the top-down traversal starts from the root page, because the
next key may be located in a subtree of the root different from the subtree covering
key x. Because of the calls of
find-next-page
, one write-latching and and 2h
1
read-latchings are performed by the traversal in the worst case.
t
7.5
Traversals for Delete Actions
The procedure call
delete
.T; x;
v
/ (Algorithm
6.8
) that implements the delete
action DŒx;
v
of transaction T uses the call
find-page-for-delete
.p; p
0
;x;y/ to
locate and write-latch the leaf page p that contains the tuple with key x and
to locate and read-latch the page p
0
that contains the key y next to x if that
key is not found in page p (when
high-key
.p/ <
1
). The procedure
find-page-
for-delete
, given as Algorithm
7.9
, also ensures that page p does not underflow
by the deletion. The procedure is analogous to the procedure
find-page-for-insert
(Algorithm
7.8
). In the same way it uses the auxiliary procedure
find-page-for-
update
.p; p
0
;x;
both
/ (Algorithm
7.7
), which is first called optimistically with
both
D
false.
Figure
7.9
represents the simple case in which only the optimistic traversal is
needed in order to accomplish the deletion: the tuple to be deleted and the next key
reside in the same page, and the page does not underflow by the deletion. Figure
7.10
represents a more complicated case.
