Databases Reference
In-Depth Information
Storage cost:
The total size is equal to:
f
d
m
−
1
m
s
C
=
P
·
+
|
s
|
.
(8)
f
m
−
1
An important advantage of the MB-tree is that the storage cost does not
necessarily reflect the owner/server communication cost. The owner, after
computing the final signature of the root, does not have to transmit all hash
values to the server, but only the database tuples. The server can recompute
the hash values incrementally by recreating the MB-tree. Since hash compu-
tations are cheap, for a small increase in the server's computation cost this
technique will reduce the owner/sever communication cost drastically.
Construction cost:
The construction cost for building an MB-tree depends on the hash function
computations and the total I/Os. Since the tree is bulk-loaded, building the
leaf level requires
N
D
hash computations of input length
|
r
|
. In addition, for
every tree node one hash of input length
f
m
·|
h
|
is computed. Since there
f
d
m
−
1
f
m
−
1
nodes on average (given height
d
m
= log
f
m
N
D
),
the total number of hash function computations, and hence the total cost for
constructing the tree is given by:
are a total of
N
I
=
s
P
·C
IO
.
C
S
|h|
+
C
c
=
N
D
·C
H
|r|
+
N
I
·C
H
f
m
|h|
+
C
(9)
VO
construction cost:
The
construction cost is dominated by the total disk I/O. Let the total
number of leaf pages accessed be equal to
N
Q
=
N
R
VO
f
m
,
d
m
= log
f
m
N
D
and
d
q
=
log
f
m
N
R
be the height of the MB-tree and the query sub-tree respectively.
In the general case the index traversal cost is:
2) +
N
Q
+
N
R
·|
r
|
m
q
C
=[(
d
m
−
d
q
+1)+2(
d
q
−
]
·C
IO
,
(10)
P
taking into account the fact that the query traversal at some point splits into
two paths. It is assumed here that the query range spans at least two leaf
nodes. The first term corresponds to the hashes inserted for the common path
of the two traversals from the root of the tree to the root of the query sub-tree.
The second term corresponds to the cost of the two boundary traversals after
the split. The last two terms correspond to the cost of the leaf level traversal
of the tree and accessing the database records.
