Information Technology Reference
In-Depth Information
Algorithm 7.6
Procedure
find-page-for-read
.p; p
0
;x;
z
/
find-page-for-fetch
.p; p
0
;
z
; false/
if
page p contains a key x with x
z
then
x the least such key in page p
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
x 1
else
{pessimistic traversal}
unlatch-and-unfix
.p/
find-page-for-fetch
.p; p
0
;
z
; true/
if
page p
0
contains a key x with x
z
then
x the least such key in page p
0
else
x 1
end if
end if
when its younger cousin q
0
is latched, thus respecting the rule that when two siblings
or cousins are to be kept latched, the elder one is latched first. The worst case of four
simultaneous read latches occurs when page p, its child q, a cousin p
0
of p,anda
child of p
0
must all be latched simultaneously in the procedure
find-next-page
.By
Lemma
7.3
, this makes at most 2h latchings in all, when the traversal is started,
using the initialized saved path, from the root page of the B-tree.
t
If the saved path has a value different from the initial value at the start of
executing a read action RŒx;
z
;
v
, then the total number of latchings needed may
be less or greater than the number stated in the above lemma. In the worst case, the
saved path dates from a time when the B-tree was higher that it is at the time the
read action starts and the entire path has to be climbed bottom-up just to end up
starting the traversal from the root page.
7.4
Traversals for Insert Actions
The procedure call
insert
.T; x;
v
/ (Algorithm
6.7
) that implements the insert
action IŒx;
v
of transaction T uses the call
find-page-for-insert
.p; p
0
;x;
v
;y/ to
locate and write-latch the leaf page p that covers key x and to locate and read-
latch the page p
0
that contains the key y next to x if that key is not found in
page p (when
high-key
.p/ <
1
). The procedure
find-page-for-insert
, given as
Algorithm
7.8
, also arranges that page p has sufficient room for the tuple .x;
v
/
to be inserted. To accomplish this arrangement, pages may need to be split, and the
tree height may have to be increased, in a top-down fashion, as will be explained in
Chap.
8
.
In the same way as the procedure
find-page-for-read
uses the auxiliary procedure
find-page-for-fetch
, the procedure
find-page-for-insert
uses an auxiliary procedure
