Information Technology Reference
In-Depth Information
Algorithm 15.4
Procedure
find-parent
.q/
fix-and-read-latch
.q/
while
q is a modified B-tree page
do
x some key in page q
unlatch-and-unfix
.q/
p the page-id of the root page
fix-and-read-latch
.p/
while
height
.p/ > 1
and
p 6D q
do
p
0
the page-id of the child of p that covers x
fix-and-read-latch
.p
0
/
if
page p
0
is modified
and
parent-link
.p
0
/ 6D p
then
unlatch-and-unfix
.p
0
/
fix-and-write-latch
.p
0
/
parent-link
.p
0
/ p
end if
unlatch-and-unfix
.p/
p p
0
end while
if
p D q
then
exit from the
while
loop
end if
fix-and-read-latch
.q/
end while
unlatch-and-unfix
.q/
We observe that the only additional restriction that must be imposed besides the
basic rules of buffering, namely, write-ahead logging and steal-and-no-force, is that
if a non-root modified B-tree page is to be relocated, then its parent page must also
be buffered and write-latched and its child link pointing to the relocated page must
be updated to reflect the new location of the child page. Most notably, we do not
enforce the requirement that all the modified child pages that are to be relocated
should be flushed before flushing the parent.
As lower-level pages of a B-tree tend to be less frequently accessed than upper-
level pages, it is likely that in the
LRU
chain, child pages appear mostly before
their parent pages, and hence children are more likely subjects of being relocated or
flushed than their parents.
15.4
Merge Trees
A
merge tree
is composed of a sequence C
0
;C
1
;:::;C
n
of B-trees (called
com-
ponents
) of growing size with the smallest one, C
0
, receiving all updates from
transactions and kept small enough to fit in main memory in its entirety. When
a component C
i
reaches a preset size limit, it is merged with the next larger
component C
iC1
, resulting in a B-tree C
0
iC1
which is then substituted for C
iC1
