hash tree算法
本文转载自：http://blog.csdn.net/yuanrxdu/article/details/22474697
Merkle Tree是Dynamo中用来同步数据一致性的算法，Merkle Tree是基于数据HASH构建的一个树。它具有以下几个特点：
1、数据结构是一个树，可以是二叉树，也可以是多叉树（本BLOG以二叉树来分析）
2、Merkle Tree的叶子节点的value是数据集合的单元数据或者单元数据HASH。
3、Merke Tree非叶子节点value是其所有子节点value的HASH值。
为了更好的理解，我们假设有A和B两台机器，A需要与B相同目录下有8个文件，文件分别是f1 f2 f3 ....f8。这个时候我们就可以通过Merkle Tree来进行快速比较。假设我们在文件创建的时候每个机器都构建了一个Merkle Tree。具体如下图:
从上图可得知，叶子节点node7的value = hash(f1),是f1文件的HASH;而其父亲节点node3的value = hash(v7, v8)，也就是其子节点node7 node8的值得HASH。就是这样表示一个层级运算关系。root节点的value其实是所有叶子节点的value的唯一特征。
假如A上的文件5与B上的不一样。我们怎么通过两个机器的merkle treee信息找到不相同的文件? 这个比较检索过程如下:
1、首先比较v0是否相同,如果不同，检索其孩子node1和node2.
2、v1 相同，v2不同。检索node2的孩子node5 node6;
3、v5不同，v6相同，检索比较node5的孩子node 11 和node 12
4、v11不同，v12相同。node 11为叶子节点，获取其目录信息。
5、检索比较完毕。
以上过程的理论复杂度是Log(N)。实际过程是大于这个复杂度的，因为不同value的节点需要每个子节点进行比较。过程描述图如下:
从上图可以得知真个过程可以很快的找到对应的不相同的文件。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
