Hi,<p>I want to build a merkle-tree for a binary JSON document store. A merkle-tree however is built bottom up, such that a hash of inner nodes is always built concatenating all children hashes.<p>However, this is costly as always all children of the ancestor nodes have to be read when we do simple update operations. That is deleting, updating or inserting a node, potentially involving a lot of I/O to read the children for each ancestor node.<p>As I want to use the hashes for speeding up comparisons of revisions of the binary XML or JSON tree structures, I instead could also use random UUIDs, which are assigned. However, with the merkle-tree we can also check integerity, which is nice.<p>When the hashes don't have to be secure, we can also use a rolling hash using a 64Bit integer (long in Java), but I guess in a 64Bit storage system there are a lot of collisions and I couldn't rely on them when doing hash comparisons for skipping whole subtrees from the traversal. Maybe it would be better with a BigInteger using 128 Bits.<p>Would you instead store UUIDs for each node? Or can I apply a secure rolling hash somehow (at most I want to store 16 bytes / 128 bits on disk I guess)?<p>kind regards
Johannes