Information Technology Reference
In-Depth Information
leaf-level page on the saved path is ignored in determining the starting page of the
top-down traversal in the procedure
find-page-for-update
.
Lemma 7.12
The latching protocol applied in the B-tree traversals for undo-insert
and undo-delete actions is deadlock-free. If no structure modifications are needed,
then in a traversal for an undo-insert or undo-delete action, at most two read latches
or one write latch and one read latch are ever held simultaneously. Even if updates
by other transactions and structure modifications on the B-tree occur during the
undoing, then in the worst case, assuming that the saved path reflects the current
height of the B-tree, one write-latching and
2h
2
read-latchings on B-tree pages
in all are performed, where
h
is the height of the B-tree. In the best case, only one
read-latching and one write-latching are performed.
Proof
Follows from the proofs of Lemmas
7.8
and
7.10
, observing that the
find-
page-for-update
.p; p
0
;x;
both
/ is only called with
both
D
false. Climbing the saved
path from level 2 up to the root and traversing the path again down to the leaf page
means 2h
2 read-latchings and one write-latching. The best case of one read latch
and one write latch in all occurs when the level-two page on the saved path is the
lowest-level non-leaf page that covers the key in question.
t
Problems
7.1
Consider executing the transaction
BR
Œx
1
; > 10;
v
1
RŒx
2
;>x
1
;
v
2
RŒx
3
;>x
2
;
v
3
RŒx
4
;>x
3
;
v
4
C
on the database indexed by the B-tree of Fig.
7.1
. Assuming that the saved path has
its initial value set by the call
initialize-saved-path
./ and that no other transactions
are in progress simultaneously, what page latchings and unlatchings of B-tree pages
occur during the execution of the transaction?
7.2
Consider executing the transaction
BI
Œ22I Œ23DŒ24C
on the database indexed by the B-tree of Fig.
7.1
. Assuming that the saved path has
its initial value set by the call
initialize-saved-path
./ and that no other transactions
are in progress simultaneously, what page latchings and unlatchings of B-tree pages
occur during the execution of the transaction?
7.3
Consider executing the transaction
BDŒ9DŒ10DŒ20AD
1
Œ20D
1
Œ10D
1
Œ9C
on the database indexed by the B-tree of Fig.
7.1
. Assuming that the saved path has
its initial value set by the call
initialize-saved-path
./ and that no other transactions
are in progress simultaneously, what page latchings and unlatchings of B-tree pages
occur during the execution of the transaction?
