Information Technology Reference
In-Depth Information
Algorithm 7.8
Procedure
find-page-for-insert
.p; p
0
;x;
v
;y/
find-page-for-update
.p; p
0
;x;false/
while
true
do
if
page p has no room for .x;
v
/
then
unlatch-and-unfix
.p; p
0
/
start-for-page-splits
.p; x;
v
/
top-down-page-splits
.p; x;
v
/
end if
if
page p contains a key greater than x
then
y the least key greater than x in page p
p
0
p
exit the
while
loop
else if
path
Œ1:
page-id
D p and
path
Œ1:
page-lsn
D P
AGE
-LSN.p/ and
path
Œ1:
high-key
D1
then
y 1
p
0
p
exit the
while
loop
else
{pessimistic traversal}
unlatch-and-unfix
.p; p
0
/
find-page-for-update
.p; p
0
;x;true/
if
page p
0
contains a key greater than x
then
y the least key greater than x in page p
0
else
y 1
end if
if
page p has room for .x;
v
/
then
exit the
while
loop
end if
end if
end while
After the optimistic traversal, if we find that page p has no room for the tuple
.x;
v
/,pagep is unlatched, and the procedure call
start-for-page-splits
.p; x;
v
/
(Algorithm
8.6
) is issued so as to locate and write-latch the highest-level ancestor
page p of the leaf page covering x that may need a structure modification to
accommodate the insertion of .x;
v
/. Then the procedure call
top-down-page-
splits
.p; x;
v
/ (Algorithm
8.7
) is used to perform a sequence of page splits, possibly
preceded by a tree-height increase, from page p down to the leaf page covering x.
The call
top-down-page-splits
.p; x;
v
/ returns with a write-latched leaf page p that
covers x and has room for .x;
v
/.
If it now turns out that page p does not contain any key greater than x,even
if it is known that
high-key
.p/ <
1
,pagep is unlatched and
find-page-for-
update
.p; p
0
;x;
both
/ is called with
both
D
true. The key y next to x can now
be determined. Because page p or its contents may have changed in the interim,
we must again check if there is room for .x;
v
/. If not, pages p and p
0
must be
unlatched, and the process be repeated, calling again
start-for-page-splits
and
top-
down-page-splits
and maybe also
find-page-for-update
, hence the “
while
true
do
”
loop in Algorithm
7.8
.
