Alan Reiner wrote: > 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.
PATRICIA Tries (aka Radix trees) have worst-case O(k), where k is the number of bits in the key. Notice that since we would storing k-bit hashes, the number of elements must be less than 2^k, or else by birthday paradox we would have a hash collision! So O(log N) <= O(k). You're right, though, that such a trie would have the property that any two trees containing the same data (leaves) will be identical. I can't think of any reason why this is useful, although I am hoping we can figure out what is triggering your intuition to desire this! I am indeed assuming that the tree will be incrementally constructed according to the canonical (blockchain) ordering of transactions, and that the balancing rules are agreed on as part of the protocol. -- Andrew Miller ------------------------------------------------------------------------------ Live Security Virtual Conference Exclusive live event will cover all the ways today's security and threat landscape has changed and how IT managers can respond. Discussions will include endpoint security, mobile security and the latest in malware threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/ _______________________________________________ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
