Information Technology Reference
In-Depth Information
Algorithm 8.7
Procedure
top-down-page-splits
.p; x;
v
/
if
page p is the root and has no 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
tree-height-increase
.p;q;x
0
;q
0
/
save-root
.p/
if
x<x
0
then
unlatch-and-unfix
.q
0
/
else
unlatch-and-unfix
.q/
q q
0
end if
save-child
.p; q/
unlatch-and-unfix
.p/
p q
end if
while
page p is a non-leaf page
do
q the page-id of the child of p that covers key x
fix-and-write-latch
.q/
if
page q has no room for .x;
v
/ (if q is a leaf page) or for an index record with a maximum-
length key (if p is a non-leaf page)
then
page-split
.p;q;x
0
;q
0
/
if
x<x
0
then
unlatch-and-unfix
.q
0
/
else
unlatch-and-unfix
.q/
q q
0
end if
end if
save-child
.p; q/
unlatch-and-unfix
.p/
p q
end while
Example 8.7
Consider executing the insert action I Œ16;
v
0
on the database of
Fig.
7.1
. Assume that the saved path has the initial value. In the procedure call
find-page-for-insert
.p; p
0
; 16;
v
0
;y/, the optimistic traversal performed by the call
find-page-for-update
.p; p
0
; 16; false/ starts at the root page p
1
and goes down to
the leaf page, p
6
, that covers key 16, saving the path p
1
!
p
3
!
p
6
so traversed:
page-id page-lsn low-key high-key max-key #records space-left
1: p
6
::: 8 17 15 6 0
2: p
3
::: 8 50 40 6 0
3: p
1
:::
1 1
99 6 0
Because page p
6
has no room for the tuple .16;
v
0
/, the write latch on the page is
released, and the call
start-for-page-splits
.p; 16;
v
0
/ is performed. As all the pages
up to and including the root page p
1
are full, the call returns with p
D
p
1
write-
latched.
