Information Technology Reference
In-Depth Information
Algorithm 6.7
Procedure
insert
.T; x;
v
/
lock
.T; x; X; commit-duration/
while
true
do
find-page-for-insert
.p; p
0
;x;
v
;y/
conditionally-lock
.T; y; X; short-duration/
if
the lock on y was granted
then
exit the
while
loop
else
m P
AGE
-LSN.p/
m
0
P
AGE
-LSN.p
0
/
unlatch-and-unfix
.p; p
0
/
lock
.T; y; X; short-duration/
fix-and-write/read-latch
.p; p
0
/
if
P
AGE
-LSN.p/ D m
and
P
AGE
-LSN.p
0
/ D m
0
or
p D p
0
and
p is a data page with
x
1
x x
2
where x
1
is the least and x
2
the greatest key in page p
and
p has room for
the tuple .x;
v
/
and
y is the least key in p greater than x
then
exit the
while
loop
else
unlatch-and-unfix
.p; p
0
/
unlock
.T; y; X; short-duration/
end if
end if
end while
if
page p contains a tuple with key x
then
unlatch-and-unfix
.p; p
0
/
return with error
else
insert-into-page
.T;p;x;
v
/
unlatch-and-unfix
.p; p
0
/
unlock
.T; y; X; short-duration/
end if
The found next key y is conditionally X-locked for short duration. If the lock
is granted, the call
insert-into-page
.T;p;x;
v
/ (Algorithm
3.1
) given in Sect.
3.6
is
used to perform and log the insertion of .x;
v
/ into page p, after which the pages
p and p
0
are unlatched and the lock on y released. Otherwise, the
P
AGE
-LSN
sof
pages p and p
0
are saved, the pages are unlatched, the lock on y is requested
unconditionally, and, when the lock is granted, the pages are relatched. The call
fix-and-write/read-latch
.p; p
0
/ is a shorthand for the call
fix-and-write-latch
.p/
followedbythecall
fix-and-read-latch
.p
0
/ if p
0
6D
p.
After relatching the pages p and p
0
, the page contents are inspected so as to find
out whether or not they can still be used to satisfy the insert action. The insert action
can be satisfied if one of the following two conditions holds:
1.
P
AGE
-LSN
.p/ and
P
AGE
-LSN
.p
0
/ have not advanced from the saved values.
2. p
D
p
0
and
P
AGE
-LSN
.p/ has advanced from the saved value, but page p is still a
data page with x
1
x
x
2
where x
1
is the least and x
2
the greatest key in page
p,pagep has room for the tuple .x;
v
/,andy is the least key in page p greater
than x.
