Information Technology Reference
In-Depth Information
(a)
(b)
Fig. 7.6
The simple case of insertion IŒx;
v
. The page to which the tuple .x;
v
/ belongs has room
for the tuple, and the tuple .y;
v
0
/ with the least key y greater than x resides in the same page. (
a
)
Before insertion (
b
) After insertion
(a)
(b)
Fig. 7.7
A more complicated case of insertion IŒx;
v
. The tuple .x;
v
/ to be inserted fits into the
covering leaf page, but the tuple with the least key y greater than x does not reside in the same
page. A pessimistic traversal is needed to locate y.(
a
) Before insertion (
b
) After insertion
find-page-for-update
.p; p
0
;x;
both
/ (Algorithm
7.7
), where the last parameter is a
boolean value indicating an optimistic traversal where only the page p is determined
(
both
D
false) or a pessimistic traversal where both p and p
0
are determined
(
both
D
true). The procedure is first called with
both
D
false, thus assuming
optimistically that the next key y resides in page p, the page that covers key x.
Figure
7.6
represents the simple case in which only the optimistic traversal is needed
in order to accomplish the insertion: the next key resides in the page that covers the
key to be inserted, and the page has room for the tuple to be inserted. Figure
7.7
represents a more complicated case.
