Databases Reference
In-Depth Information
P
f
log
f
k
f
e
−
1
k
−
1
[
f
k
(
|
k
|
|
p
|
|
h
|
−|
k
|
+
+
)
]+
f
k
−
1
[
f
e
(
|
k
|
+
|
p
|
+
|
h
|
)
−|
k
|
]
.
(13)
First, a suitable
f
k
is chosen such that the requirements for authentication
cost and storage overhead are met. Then, the maximum value for
f
e
satisfying
(13) can be determined.
Storage cost:
The storage cost is equal to:
f
d
e
e
−
1
e
C
s
=
P
·
|
s
|
.
+
(14)
f
e
−
1
Construction cost:
The total construction cost is the cost of constructing all the embedded trees
plus the I/Os to write the tree back to disk. Given a total of
N
I
=
f
d
e
−
1
f
e
−
1
nodes in the tree and
N
i
=
f
d
k
−
1
nodes per embedded tree, the cost is:
f
k
−
1
s
P
·C
IO
.
C
S
|h|
+
C
e
c
=
N
D
·C
H
|r|
+
N
I
C
·
N
i
·C
H
f
k
|h|
+
(15)
It should be mentioned here that the cost for constructing the
EMB
−
-tree is
exactly the same, since in order to find the hash values for the index entries of
the trees one needs to instantiate all embedded trees. The cost of the
EMB
∗
-
tree is somewhat smaller than (15), due to the smaller number of nodes in the
embedded trees.
VO
construction cost:
The
construction cost is dominated by the total I/O for locating and
reading all the nodes containing the query results. Similarly to the MB-tree
case:
VO
2) +
N
Q
+
N
R
·|
r
|
q
=[(
d
e
−
C
d
q
+1)+2(
d
q
−
]
·C
IO
,
(16)
P
N
R
where
d
q
is the height of the query sub-tree and
N
Q
=
f
e
is the number of
leaf pages to be accessed. Since the embedded trees are loaded with each node,
the querying computation cost associated with finding the needed hash values
is expected to be dominated by the cost of loading the node in memory, and
hence it is omitted. It should be restated here that for the
EMB
∗
-tree the
expected
construction cost will be smaller, since not all embedded tree
searches will reach the leaf level of the structure.
VO
