Databases Reference
In-Depth Information
1
f
d
m
−i
m
f
d
m
−i
m
)
k
]. Hence, for a batch of
k
updates the total expected number of nodes that will be affected is:
·
P
i
(
X
), where
P
i
(
X
)=[1
−
(1
−
d
m
−
1
1
f
i
m
f
i
m
[1
)
k
]
.
E
{
X
}
=
−
(1
−
(20)
i
=0
Hence, the expected MB-tree update cost for batch updates is
u
=
k
C
·H
|r|
+
E
{
X
}·
(
H
f
m
|h|
+
C
IO
)+
S
|h|
.
(21)
In order to understand better the relationship between the per-update
approach and the batch-update, we can find the closed form for
E
{
X
}
as
follows:
d
m
−
1
i
=0
(
f
i
m
−
1
f
i
m
f
i
m
(1
)
k
)
−
=
d
m
−
1
i
=0
f
i
m
(1
f
i
m
)
k
)
1
−
(1
−
−
x
=0
x
(
=
d
m
−
1
i
=0
f
i
m
[1
f
i
m
)
x
]
1
−
x
=0
x
(
=
d
m
−
1
i
=0
f
i
m
−
d
m
−
1
1)
x
(
f
i
m
)
x−
1
1
−
i
=0
=
kd
m
−
x
=2
x
(
1)
x
d
m
−
1
i
=0
f
i
m
)
x−
1
1
−
(
=
kd
m
−
x
=2
x
(
)
x−
1
1
−
(
f
m
)
x−
1
The second term quantifies the cost decrease afforded by the batch update
operation, when compared to the per update cost.
For non-uniform updates to the database, the batch updating technique is
expected to work well in practice given that in real settings updates exhibit
a certain degree of locality. In such cases one can still derive a similar cost
analysis by modelling the distribution of updates.
1
f
d
m
1)
x
1
−
(
−
The Embedded MB-tree
The analysis for the EMB-tree is similar to the one for MB-trees. The update
cost for per tuple updates is equal to
k
u
, where
u
=
·C
C
H
|r|
+
d
e
log
f
k
f
e
·
(
S
|h|
, once again assuming that no reorganizations to the tree
occur. Similarly to the MB-tree case the expected cost for batch updates is
equal to:
H
f
k
|h|
+
C
IO
)+
u
=
k
C
·H
|r|
+
E
{
X
}·
log
f
k
f
e
·
(
H
f
k
|h|
+
C
IO
)+
S
|h|
.
(22)
Discussion
For the ASB-tree, the communication cost for updates between owner and
servers is bounded by
E
, and there is no possible way to reduce this cost
as only the owner can compute signatures. However, for the hash based index
structures, there are a number of options that can be used for transmitting
{
K
}|
s
|
