Information Technology Reference
In-Depth Information
on x cannot be granted immediately, the
P
AGE
-LSN
s of pages p and p
0
are saved,
the pages are unlatched, the lock is requested unconditionally, and, when the lock is
granted, the pages are relatched.
The call
fix-and-read-latch
.p; p
0
/ is a shorthand for the call
fix-and-read-
latch
.p/ followed by the call
fix-and-read-latch
.p
0
/ if p
0
6D
p. Similarly, the call
unlatch-and-unfix
.p; p
0
/ is a shorthand for the call
unlatch-and-unfix
.p/ followed
by the call
unlatch-and-unfix
.p
0
/ if p
0
6D
p.
After relatching the pages p and p
0
, the page contents are inspected so as to find
out whether or not they can still be used to satisfy the read action. The read action
can be satisfied if one of the following two conditions holds:
1.
P
AGE
-LSN
.p/ and
P
AGE
-LSN
.p
0
/ have not advanced from the saved values, that is,
the pages have not been modified in the interim.
2. p
D
p
0
and
P
AGE
-LSN
.p/ has advanced from the saved value, but page p is still
a data page, and x is the least key in page p with x
z
z
1
,where
z
1
is the least
keyinpagep.
In case (1) it is clear that the read action can be satisfied from pages p
and p
0
. Recall that the pages p
0
and p, determined by the call
find-page-for-
read
.p; p
0
;x;
z
/, cover two successive subranges of the key space and that the
key range covered by a page can change only if the page is modified and hence its
P
AGE
-LSN
is advanced.
Also in case (2), even if one of the pages p and p
0
has been modified in the
interim, so that the
P
AGE
-LSN
value of one of these pages is greater than the saved
value, it may still be possible to satisfy the read action, provided that we can be sure
that the pages p and p
0
together still cover the key range from
z
to the least key x
with x
z
. This is true at least in the case that p
D
p
0
and x is the least key in page
p with x
z
z
1
,where
z
1
is the least key in page p. Note that if p
6D
p
0
and one
of the pages has been modified in the interim, it may no longer be the case that these
are the pages that together cover the range from
z
to the least key x with x
z
.
If neither (1) nor (2) holds, we cannot be sure that pages p and p
0
can be used
to satisfy the read action; hence we must unlatch pages p and p
0
, unlock key x,
and repeat the search for the correct target pages and the correct target key by
performing again the call
find-page-for-read
.p; p
0
;x;
z
/, locking the found key
x conditionally, and so on.
The insert action IŒx;
v
is implemented by the procedure
insert
.T; x;
v
/ (Algo-
rithm
6.7
). First, the key x is unconditionally X-locked for commit duration. Then
the call
find-page-for-insert
.p; p
0
;x;
v
;y/ is used to locate and write-latch the data
page p that covers key x and to locate and read-latch the data page p
0
that contains
the key y next to x if that key is not found in page p (and
high-key
.p/ <
1
).
If p
6D
p
0
, the pages p and p
0
cover two successive subranges of the key space.
The call also ensures (by appropriate structure modifications) that page p does not
overflow by the insertion, that is, there is room for the tuple .x;
v
/ in page p.In
Sect.
7.4
we give an implementation for the call
find-page-for-insert
.p; p
0
;x;
v
;y/
in the case of a sparse B-tree.
