Information Technology Reference
In-Depth Information
2. Page p, if not the root, has room for .x;
v
/ (if p is a leaf page) or for an index
record with a maximum-length key (if p is a non-leaf page).
Again we first use just the information stored in the saved path to determine an
approximation for such a page p, write-latch it, and check if it satisfies the above
conditions; if not, we unlatch the page and probe the page at the next higher level
on the saved path.
Once the starting page p has been determined, a sequence of page splits, possibly
preceded by a tree-height increase, is performed top-down along the path down to
the page that currently covers key x. This is done by the procedure call
top-down-
page-splits
.p; x;
v
/ (Algorithm
8.7
), where p is the page-id of the write-latched
starting page. The call determines again the path down to the leaf page covering
key x, performs the structure modifications needed level-by-level, and saves the
path.
Algorithm 8.6
Procedure
start-for-page-splits
.p; x;
v
/
i the least index for which either
path
Œi :
page-id
is the page-id of the root or
path
Œi :
space-left
is sufficient for .x;
v
/ (if i D 1) or for an index record with a maximum-
length key (if i>1)
p
path
Œi :
page-id
fix-and-write-latch
.p/
while
page p is not the root
do
if
P
AGE
-LSN.p/ D
path
Œi :
page-lsn
and
path
Œi :
low-key
x<
path
Œi :
high-key
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
if
page p has room for .x;
v
/ (if p is a leaf page) or for an index record with a maximum-
length key (if p is a non-leaf page)
then
exit the
while
loop
end if
end if
unlatch-and-unfix
.p/
i i C1
p
path
Œi :
page-id
fix-and-write-latch
.p/
end while
if
page p is the root
then
save-root
.p/
end if
