Information Technology Reference
In-Depth Information
Fig. 15.1
Merging entire trees in a three-level merge tree
(Fig.
15.1
). The idea is that the new tree C
iC1
resulting from the merge is built
into a new disk space using large sequential writes.
In merging components C
i
and C
iC1
, the resulting component C
0
iC1
can be built
in a manner similar to that presented for B-tree loading in Sect.
8.8
. Because the
components C
i
with i>0are only updated via merging and never receive any
normal updates, we use a fill-factor near 100%, so that when a page is split, only
two records go from a full page to the new sibling page. A modification of the B-tree
loading algorithm uses sequential writes (Problem
15.1
).
The following conditions must be satisfied by a merge tree on relation r.
X
;V/:
1. Each component C
i
indexes a set of tuples .x;
v
/ that either currently belong to r
or used to belong to r . In addition, a component C
i
with i<nmay index tuples
.x;
?
/ where
?
is a special
delete marker
indicating that a tuple with key x used
to belong to r but was deleted.
2. The keys x are unique within each C
i
.
3. If .x;
v
/ currently belongs to r , then it is indexed by the component C
i
with the
least i such that C
i
indexes a tuple with key x.
