Ask HN: Merkle Trees / Rolling Hashes for XML or JSON

Hi, 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. 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. 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. 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. 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)? kind regards Johannes