Information Technology Reference
In-Depth Information
Fig. 6.6
Data pages p
1
;p
2
;:::;p
n
covering the key space Œ1;1/ partitioned into disjoint key
ranges .1;h
1
/; Œh
1
;h
2
/;:::;Œh
n
1
;1/
Algorithm 6.6
Procedure
read
.T;x;
z
;
v
/
while
true
do
find-page-for-read
.p; p
0
;x;
z
/
conditionally-lock
.T; x; S; commit-duration/
if
the lock on x was granted
then
exit the
while
loop
else
m P
AGE
-LSN.p/
m
0
P
AGE
-LSN.p
0
/
unlatch-and-unfix
.p; p
0
/
lock
.T; x; S; commit-duration/
fix-and-read-latch
.p; p
0
/
if
P
AGE
-LSN.p/ D m
and
P
AGE
-LSN.p
0
/ D m
0
or
p D p
0
and
p isadatapage
and
x
is the least key in page p with x
z
z
1
where
z
1
is the least key in page p
then
exit the
while
loop
else
unlatch-and-unfix
.p; p
0
/
unlock
.T; x; S; commit-duration/
end if
end if
end while
if
x D1
then
v
0
else
v
the value of the tuple with key x
end if
unlatch-and-unfix
.p; p
0
/
assume that the key range covered by page p
i
can change only if the page itself is
modified and hence its
P
AGE
-LSN
is advanced.
The read action RŒx;
z
;
v
is implemented by the procedure
read
.T;x;
z
;
v
/
(Algorithm
6.6
). In this procedure, the call
find-page-for-read
.p; p
0
;x;
z
/ is used
to locate and read-latch the data page p that covers key
z
and the data page p
0
that
holds the key to be read, that is, the least key x in the database with x
z
.Ifp
0
6D
p,
the key ranges Œl
0
;h
0
/ and Œl; h/ covered by these pages are two successive subranges
of the key space, so that l
0
<h
0
D
l<h.
In Sect.
7.3
we give an implementation for the procedure call
find-page-for-
read
.p; p
0
;x;
z
/ in the case the physical database structure is a sparse B-tree. Then
the page p
0
is either p orthepagenexttop at the leaf level of the B-tree. If the lock
