Databases Reference
In-Depth Information
values of the residual entries to the left and to the right parts of the boundary
leaves. The result is also increased with one tuple to the left and one to the
right of the lower-bound and upper-bound of the query result respectively,
for completeness verification. Finally, the signed root of the tree is inserted as
well. An example query traversal is shown in Figure 4.
return h
i
ρ
1
...
I
1
I
2
I
3
I
4
I
5
I
6
I
7
I
8
...
...
L
1
L
2
L
3
L
4
L
5
L
6
L
7
L
8
L
9
L
10
L
11
L
12
return h
i
ρ
o
return r
i
Fig. 4.
A query traversal on an MB-tree. At every level the hashes of the residual
entries on the left and right boundary nodes need to be returned.
The client can iteratively compute all the hashes of the sub-tree corre-
sponding to the query result, all the way up to the root using the
.The
hashes of the query results are computed first and grouped into their corre-
sponding leaf nodes
4
, and the process continues iteratively, until all the hashes
of the query sub-tree have been computed. After the hash value of the root
has been computed, the client can verify the correctness of the computation
using the owner's public key
PK
and the signed hash of the root. It is easy
to see that since the client is forced to recompute the whole query sub-tree,
both correctness and completeness is guaranteed. It is interesting to note here
that one could avoid building the whole query sub-tree during verification by
individually signing all database tuples as well as each node of the
B
+
-tree.
This approach, called VB-tree, was proposed in [22] but it is subsumed by
the ASB-tree. Another approach that does not need to build the whole tree
appeared in [32]. The analytical cost models of the MB-tree are as follows:
VO
Node fanout:
The node fanout in this case is:
P
−|
p
|−|
h
|
f
m
=
+1
.
(7)
|
k
|
+
|
p
|
+
|
h
|
Notice that the maximum node fanout of the MB-tree is considerably smaller
than that of the ASB-tree, since the nodes here are extended with one hash
value per entry. This adversely affects the total height of the MB-tree.
4
Extra node boundary information can be inserted in the
VO
for this purpose with
a very small overhead.
