On 06/19/2012 02:18 PM, Mark Friedenbach wrote:
If we were to use a raw trie structure, then we'd have all the
above
issues solved: a trie has the same configuration no matter
how elements
are inserted or deleted, and accesses to elements in the tree
are
constant time -- O(1). There is no such thing as an
unbalanced trie.
But overall space-efficiency is an issue.
A PATRICIA tree/trie would be ideal, in my mind, as it also
has a
completely deterministic structure, and is an
order-of-magnitude more
space-efficient. Insert, delete and query times are still
O(1).
However, it is not a trivial implementation. I have
occasionally looked
for implementations, but not found any that were satisfactory.
No, a trie of any sort is dependent upon distribution of
input data for balancing. As Peter
Todd points out, a malicious actor could construct
transaction or address hashes in such a way as to grow some
segment of the trie in an unbalanced fashion. It's not much
of an attack, but in principle exploitable under particular
timing-sensitive circumstances.
Self-balancing
search trees (KVL, RB, 2-3-4, whatever) don't suffer from
this problem.
Mark
I was using "unbalanced" to refer to "query time" (and also
insert/delete time). If your trie nodes branch based on the next
byte of your key hash, then the max depth of your trie is 32.
Period. No one can do anything to ever make you do more than 32
hops to find/insert/delete your data. And if you're using a raw
trie, you'll always use
exactly 32 hops regardless of the
distribution of the underlying data. Hence, the trie structure is
deterministic (history-independent) and cannot become unbalanced in
terms of access time.
My first concern was that a malicious actor could linearize parts of
the tree and cause access requests to take much longer than log(N)
time. With the trie, that's not only impossible, you're actually
accessing in O(1) time.
However, you are right that disk space can be affected by a
malicious actor. The more branching he can induce, the more branch
nodes that are created to support branches with only one leaf.