Information Technology Reference
In-Depth Information
(a)
(b)
Fig. 7.8
Insert action IŒ4;
v
0
on the B-tree of Fig.
7.1
.(
a
) In the optimistic traversal, the path
p
1
! p
2
! p
4
is traversed, leaving page p
4
write-latched. (
b
)Aspagep
4
does not contain the
least key greater than key 4, a pessimistic traversal is performed from the lowest-level page, p
2
,
that covers 4 and whose subtree contains a key greater than 4, yielding pages p
4
and p
5
; finally the
tuple .4;
v
0
/ is inserted into p
4
The child page p
4
of page p
2
is write-latched and the call
find-next-
page
.p
2
;p
4
;> 4;p
2
;q
0
/ is performed, returning with q
0
D
p
5
. Thus, the call
find-page-for-update
.p; p
0
;4;true/ returns with page p
D
p
4
write-latched and
page p
0
D
p
5
read-latched, and the call
find-page-for-insert
.p; p
0
;4;
v
0
;y/ returns
with y
D
5. The next key y can now be locked and the tuple .4;
v
0
/ be inserted into
page p
D
p
4
(Fig.
7.8
b).
In a more complicated situation, the leaf page covering the key of the tuple to
be inserted does not have room for the tuple. This happens with the insert action
I Œ16;
v
0
. In this case, the leaf page, p
6
, covering the key has no room for the tuple,
besides that the next key resides in the next page. This situation will be considered
in detail in Example
8.7
.
t
Lemma 7.8
The latching protocol applied in the B-tree traversals for insert actions
is deadlock-free. If the leaf page covering key
x
has room for tuple
.x;
v
/
, then in the
traversal for insert action
IŒx;
v
, at most four read latches or one write latch and
three read latches are ever held simultaneously. If the X lock on the key next to
x
is
granted immediately as a result of the conditional lock call in the procedure insert
(Algorithm
6.7
) and no updates by other transactions or structure modifications on
the B-tree occur during the insertion and the leaf page covering key
x
has room for
the tuple
.x;
v
/
and the saved path has its initial value, then in the worst case two
write-latchings and
3h
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 latching (write-
latching) is performed.
Proof
In Algorithms
7.5
,
7.7
,and
7.8
, no read latch is ever upgraded to a write latch,
and while a page is kept latched, no latch is requested on its parent or elder sibling or
elder cousin. By Lemma
8.9
, the latching protocol applied in the procedures
start-
for-page-splits
and
top-down-page-splits
is deadlock-free. The worst case of one
