Information Technology Reference
In-Depth Information
Algorithm 7.5
Procedure
find-next-page
.p;q;
z
;p
0
;q
0
/
if
page q contains a key x with x
z
then
q
0
q
else if
q is the youngest child of p
then
if
p
0
D p
then
{case (a)}
q
0
q
else
{case (b)}
q
0
the page-id of the eldest child of p
0
fix-and-read-latch
.q
0
/
end if
else
{case (c)}
q
0
the page-id of the next younger sibling of q
fix-and-read-latch
.q
0
/
end if
if
p
0
6D p
then
unlatch-and-unfix
.p
0
/
end if
Fig. 7.4
Different situations
for the call
find-next-page
.p;q;
z
;p
0
;q
0
/.
(
a
) p
0
D p and q is the
youngest child of page p;
(
b
) p
0
6D p and page q is the
youngest child of page p;
(
c
)pageq is not the youngest
child of page p
a
b
c
Example 7.5
Consider executing the read action RŒx; > 7;
v
by the call
read
.T;x;>7;
v
/ (Algorithm
6.6
) on the database indexed by the B-tree of Fig.
7.1
.
Assume that the saved path has the initial value resulting from the call
initialize-
saved-path
./. In the procedure call
find-page-for-read
.p; p
0
;x;>7/, an optimistic
traversal is first performed with the call
find-page-for-fetch
.p; p
0
;>7;false/, starting
at the root page p
1
and going down to the leaf page, p
D
p
5
, that covers key 7.
Latch-coupling with read latches is used, retaining a read latch on page p
5
.The
traversed path p
1
!
p
2
!
p
5
(shown in Fig.
7.5
a) is saved:
