Hash Tree

BitTorrent中的数据块校验方式改进：Merkle Hashing Tree
                
                
第一次见到Hash Tree（又称为Merkle Hashing Tree，这是以发现人来命名）
但是Hash Tree第一次被NoSQL提到是在亚马逊的Dynamo系统上，用来作为节点同步的算法。
Hash Tree有下面几个特性：
（1）可以在O(1)的情况下发现不同
（2）可以在O(logN)的情况下定位到具体位置。
接触这个数据结构很久了，但是一直有个疑惑，就是Hash Tree是对固定数目的叶子节点起作用，那么对于一个分布式文件系统来说，这个数目是不固定的。问题就在于如何把文件系统中的这个不确定因素变成一个确定的。
对于具体的系统应该采用具体的方案，对于Dynamo这样的基于一致性Hash的系统来说，这里的解决办法就是将集合作为叶子节点，一个叶子节点的hash是一个范围的key值，如果这个key的范围是2^4 = 16个，那么叶子节点最多有16个，这个树最多是4层。
写点自己的认识，欢迎朋友们指正，共同提高。