Databases Reference
In-Depth Information
tree, the total number of values inserted in the
VO
per node is reduced to
(
f
k
−
1)
d
k
.
To authenticate the query results the client uses the normal MB-tree au-
thentication algorithm to construct the hash value of the root node of each
embedded tree (assuming that proper boundary information has been included
in the
for separating groups of hash values into different nodes) and then
follows the same algorithm once more for computing the final hash value of
the root of the EMB-tree.
The EMB-tree structure uses extra space for storing the index levels of
the embedded trees. Hence, by construction it has increased height compared
to the MB-tree due to smaller fanout
f
e
. A first, simple optimization for
improving the fanout of the EMB-tree is to avoid storing the embedded trees
altogether. Instead, each embedded tree can be instantiated by computing
fewer than
f
e
/
(
f
k
−
VO
1) hashes on the fly, only when a node is accessed during
the querying phase. We call this the
EMB
−
-tree. The
EMB
−
-tree is logically
the same as the EMB-tree, however its physical structure is equivalent to an
MB-tree with the hash values computed differently. The querying algorithm
of the
EMB
−
-tree is slightly different than that of the EMB-tree in order to
take into account the conceptually embedded trees. With this optimization
the storage overhead is minimized and the height of the
EMB
−
-tree becomes
equal to the height of the equivalent MB-tree. The trade-off is an increased
computation cost for constructing the
VO
. However, this cost is minimal as
the number of embedded trees that need to be reconstructed is bounded by
the height of the
EMB
−
-tree.
As a second optimization, one can create a slightly more complicated em-
bedded tree to reduce the total size of the index levels and increase fanout
f
e
.
We call this the
EMB
∗
-tree. Essentially, instead of using a
B
+
-tree as the
base structure for the embedded trees, one can use a multi-way search tree
with fanout
f
k
while keeping the structure of the external EMB-tree intact.
The embedded tree based on
B
+
-trees has a total of
N
i
=
f
d
k
−
1
f
k
−
1
nodes while,
for example, a B-tree based embedded tree (recall that a B-tree is equivalent
to a balanced multi-way search tree) would contain
N
i
=
f
e
−
1
f
k
−
1
nodes instead.
A side effect of using multi-way search trees is that the cost for querying the
embedded tree on average will decrease, since the search for a particular key
might stop before reaching the leaf level. This will reduce the expected cost
of
construction substantially. Below we give the analytical cost models of
the EMB-tree. The further technical details and the analytical cost models
associated with the
EMB
∗
-tree and
EMB
−
-tree are similar to the EMB-tree
case and can be worked out similarly.
VO
Node fanout:
For the EMB-tree, the relationship between
f
e
and
f
k
is given by:
