Information Technology Reference
In-Depth Information
(a)
(b)
Fig. 7.5
Performing the read action RŒx; >7;
v
on the B-tree of Fig.
7.1
. The pages visited (
a
)in
the optimistic traversal and (
b
) in the pessimistic traversal that not only determines the page p
5
that covers key 7 but also page p
6
that covers the key 9 next to key 7
page-id
page-lsn
low-key
high-key
max-key
#records
space-left
1:
p
5
:::
5
8
7
2
:::
2:
p
2
:::
1
8
5
2
:::
3:
p
1
:::
1 1
99
6
0
Because page p
5
does not contain a key greater than 7, the page is unlatched and
the pessimistic call
find-page-for-fetch
.p; p
0
;>7;true/ is performed.
Using the path saved from the previous traversal, we determine the first page to
be latched. It is page p
1
D
path
Œ3:
page-id
, because i
D
3 is the least index with
path
Œi :
low-key
7<
path
Œi :
high-key
and with either
path
Œi :
high-key
D1
or
path
Œi :
max-key
>7. Thus, the second top-down traversal is started at the root.
Both the page p that covers key 7 and the page p
0
that contains the key next
to 7 are determined. The procedure
find-next-page
.p;q;>7;p
0
;q
0
/ is first called
with arguments p
D
p
1
, q
D
p
2
and p
0
D
p
1
, returning q
0
D
p
3
,andthen
with arguments p
D
p
2
, q
D
p
5
and p
0
D
p
3
, returning q
0
D
p
6
. Thus the call
find-page-for-fetch
.p; p
0
;> 7;true/ returns with p
D
p
5
and p
0
D
p
6
, meaning
that the call
find-page-for-read
.p; p
0
;x;>7/returns with p
D
p
5
and p
0
D
p
6
and
x
D
9. Here pages p
5
and p
6
are read-latched. See Fig.
7.5
b.Thetuplewithkey9
can now be read.
t
Lemma 7.6
The latching protocol applied in the B-tree traversals for read actions
is deadlock-free. At most four pages are kept latched simultaneously. For a B-tree
of height
h
,atmost
2h
latchings on B-tree pages are performed in all for a read
action
RŒx;
z
;
v
implemented by the call read
.T;x;
z
;
v
/
with an initialized saved
path, provided that the S lock on key
x
is granted immediately as a result of the
conditional lock call.
Proof
In Algorithms
7.4
-
7.6
, only read latches are acquired, and while a page is
kept latched, no latch is requested on its parent or elder sibling. Also note that in
the call
find-next-page
.p;q;
z
;p
0
;q
0
/ (Algorithm
7.5
), the page q is already latched
