Information Technology Reference
In-Depth Information
Algorithm 7.7
Procedure
find-page-for-update
.p; p
0
;x;
both
/
i the least index with
path
Œi :
low-key
x<
path
Œi :
high-key
and with either
path
Œi :
high-key
D1or
path
Œi :
max-key
>x
p
path
Œi :
page-id
while
p is not the page-id of the root page
do
if
i D 1
then
fix-and-write-latch
.p/
else
fix-and-read-latch
.p/
end if
if
P
AGE
-LSN.p/ D
path
Œi :
page-lsn
and
path
Œi :
low-key
x<
path
Œi :
high-key
and
either
path
Œi :
high-key
D1or
path
Œi :
max-key
>x
or
p is a B-tree page with x
1
x<x
2
for
the keys x
1
and x
2
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 x
if
height
.p/ D 2
then
fix-and-write-latch
.q/
else
fix-and-read-latch
.q/
end if
save-child
.p; q/
if
both
then
find-next-page
.p;q;>x;p
0
;q
0
/
p
0
q
0
else
p
0
q
end if
unlatch-and-unfix
.p/
p q
end while
