Information Technology Reference
In-Depth Information
the saved high key of the parent p only in case (1), in which case it can be trusted
because
P
AGE
-LSN
.p/
D
path
Œi :
page-lsn
. The starting page p is determined as a
result of the first
while
loop of Algorithm
7.4
.
Next the path from the starting page down to the leaf page that covers key
z
is
traversed using latch-coupling with read latches and saving the path so traversed.
This is done in the second
while
loop of Algorithm
7.4
.If
both
D
true, then at each
page p visited, we also keep track of the root p
0
of the subtree that may contain
the least key x with x
z
should the key not reside in the subtree rooted at p
(that covers key
z
). The page p
0
, if distinct from p, is always the page next to p
at the same level. At the start of the traversal, p
0
D
p. When advancing from p to
its child page q, the call
find-next-page
.p;q;
z
;p
0
;q
0
/ (Algorithm
7.5
)isusedto
determine the page q
0
whose subtree may contain the searched key x should the key
not reside in the subtree rooted at q (Fig.
7.4
). If
both
D
false, the call
find-page-
for-fetch
.p; p
0
;
z
;
both
/ returns with p
0
D
p.
Algorithm 7.4
Procedure
find-page-for-fetch
.p; p
0
;
z
;
both
/
i the least
index
with
path
Œi :
low-key
z
<
path
Œi :
high-key
and with either
path
Œi :
high-key
D1or
path
Œi :
max-key
z
p
path
Œi :
page-id
while
p is not the page-id of the root page
do
fix-and-read-latch
.p/
if
P
AGE
-LSN.p/ D
path
Œi :
page-lsn
and
path
Œi :
low-key
z
<
path
Œi :
high-key
and
either
path
Œi :
high-key
D1or
path
Œi :
max-key
z
or
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
then
exit the
while
loop
else
unlatch-and-unfix
.p/
i i C1
p
path
Œi :
page-id
end if
end while
p
0
p
if
page p is the root
then
save-root
.p/
end if
while
page p is a non-leaf page
do
q the page-id of the child page of p that covers key
z
fix-and-read-latch
.q/
save-child
.p; q/
if
both
then
find-next-page
.p;q;
z
;p
0
;q
0
/
p
0
q
0
else
p
0
q
end if
unlatch-and-unfix
.p/
p q
end while
