Information Technology Reference
In-Depth Information
Algorithm 8.9
Procedure
top-down-page-merges
.p; x/
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 only the required minimum number of records
then
if
q is the youngest child of p
then
q
00
the page-id of the next elder sibling of q
unlatch-and-unfix
.q/
fix-and-write-latch
.q
00
/
fix-and-write-latch
.q/
q
0
q
q q
00
else
q
0
the page-id of the next younger sibling of q
fix-and-write-latch
.q
0
/
end if
if
the records in pages q and q
0
all fit into a single page
then
if
p is the root page and q and q
0
are its only children
then
tree-height-decrease
.p;q;x
0
;q
0
/
save-root
.p/
else
page-merge
.p;q;x
0
;q
0
/
save-child
.p; q/
unlatch-and-unfix
.p/
p q
end if
else
records-redistribute
.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
save-child
.p; q/
unlatch-and-unfix
.p/
p q
end if
end if
end while
Example 8.8
Consider executing the delete action DŒ3;
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-delete
.p; p
0
;3;y/, the optimistic traversal performed by the call
find-
page-for-update
.p; p
0
;3;false/ starts at the root page p
1
and goes down to the leaf
page, p
4
, that covers key 3, saving the path p
1
!
p
2
!
p
4
so traversed:
