Information Technology Reference
In-Depth Information
(a)
(b)
Fig. 7.10
A case of deletion DŒx;
v
where a pessimistic traversal is needed. The leaf page
containing .x;
v
/ does not underflow by the deletion, but the tuple with the least key y greater
than x does not reside in the same page. (
a
) Before deletion (
b
) After deletion
If the leaf page p determined by the optimistic traversal would underflow
by the deletion of a tuple, page p is unlatched, the procedure call
start-for-
page-merges
.p; x/ (Algorithm
8.8
) is issued so as to locate and write-latch the
highest-level ancestor page p of the page covering x that may need a structure
modification to accommodate the deletion. Then the procedure call
top-down-page-
merges
.p; x/ (Algorithm
8.9
) is used to perform a sequence of page merges or
records redistributes, possibly preceded by a tree-height decrease, from page p
down to the leaf page covering x. The call
top-down-page-merges
.p; x/ returns with
a write-latched leaf page p that covers x and does not underflow by the deletion of
a tuple.
Then the key y next to x is determined, possibly needing the unlatching of page
p and the issuing of the call
find-page-for-update
.p; p
0
;x;
both
/ with
both
D
true.
As in the case of traversing for an insert action, the process may have to be repeated,
if the page p so returned would underflow by the deletion.
Example 7.9
Consider executing the action DŒ7;
v
0
by the call
delete
.T; 7;
v
0
/
(Algorithm
6.8
) on a database indexed by the B-tree of Fig.
7.1
. Assume that the
saved path has the initial value resulting from the call
initialize-saved-path
./.Inthe
procedure call
find-page-for-delete
.p; p
0
;7;y/, an optimistic traversal performed by
the call
find-page-for-update
.p; p
0
;7;false/ starts at the root page p
1
and goes down
to the leaf page, p
D
p
5
, that covers key 7. Latch-coupling is used, with read latches
acquired on the non-leaf pages p
1
and p
2
and a write latch on the leaf page p
5
.The
traversed path p
1
!
p
2
!
p
5
is saved:
page-id
page-lsn
low-key
high-key
max-key
#records
space-left
1:
p
5
:::
5
8
7
3
:::
2:
p
2
:::
1
8
5
2
:::
3:
p
1
:::
1 1
99
6
0
Page p
5
can accommodate the deletion but does not contain a key greater than 7
(Fig.
7.11
a). Hence the write latch on the page is released and the call
find-page-
for-update
.p; p
0
;7;true/ is performed. Using the above-saved path, we determine
