Information Technology Reference
In-Depth Information
(a)
(b)
Fig. 7.3
Traversal performed for RŒx; >
z
;
v
(
a
) in the case when tuples with keys
z
and x reside
in the same leaf page, (
b
) in the case when they reside in different leaf pages
for-read
is given as Algorithm
7.6
. It uses an auxiliary procedure
find-page-for-
fetch
.p; p
0
;
z
;
both
/ (Algorithm
7.4
), where the last parameter is a boolean value
indicating whether an optimistic traversal (
both
D
false) or a pessimistic traversal
(
both
D
true) is to be performed. In an optimistic traversal, only the page p is
determined, while in a pessimistic traversal both p and p
0
are determined.
The procedure
find-page-for-fetch
.p; p
0
;
z
;
both
/ is first called with
both
D
false, thus assuming optimistically that the key x to be read resides in page p,the
page that covers key
z
. If it turns out that page p does not contain any key x with
x
z
, even if it is known that
high-key
.p/ <
1
,pagep is unlatched and
find-
page-for-fetch
.p; p
0
;
z
;
both
/ is called with
both
D
true. Page p must be unlatched
before starting the new traversal, because latching an ancestor of a latched page
could lead to a deadlock. The new traversal must search both for the page that covers
z
and for the page that covers the least key x with x
z
, because after unlatching p
both pages may change in the interim.
The procedure
find-page-for-fetch
.p; p
0
;
z
;
both
/ uses the saved path to deter-
mine the lowest-level page p at which to start the traversal for the search for the
leaf page covering key
z
. The first approximation for p is determined using only the
information stored in the saved path. That page p is latched and then, if different
from the root, checked if it satisfies one of the two conditions below; if not, the page
is unlatched, and the page at the next higher level on the saved path is probed. In the
following, i is the index of the page on the saved path.
1.
P
AGE
-LSN
.p/
D
path
Œi :
page-lsn
and
path
Œi :
low-key
z
<
path
Œi :
high-key
and, in addition, either
path
Œi :
high-key
D1
or
path
Œi :
max-key
z
.
2.
P
AGE
-LSN
.p/ >
path
Œi :
page-lsn
but p is a B-tree page with x
2
z
x
1
for the
keys x
2
and x
1
of some records in page p.
Both of these conditions ensure that the least key x with x
z
,ifsuchakeyexists,
is found in the subtree rooted at page p. Both conditions also ensure that when the
path down from p is traversed and the path is saved using the
save-child
.p; q/ call,
the high key for q is correctly determined. Note that the high key can come from
