这是我最近在研究一篇论文的时候发现的，开始不知道是什么，所以查了些资料。

What is Merkle tree?

Merkle tree是一种树，网上大都称Merkle Hash tree，这是因为它所构造的所有Merkle tree节点都是Hash值。

Merkle tree具有以下的特点：

1.它是一种树，可以是二叉树，也可以是多叉树，无论是几叉树，它都具有树结构的所有特点；

2.Merkle tree叶子节点上的value值是由你指定的，这主要看你的设计了，如Merkle Hash tree会将数据的Hash值作为叶子节点的值；

3.非叶子节点的value是根据它下面所有的叶子节点的值，然后按照一定的算法计算而得出。如Merkle Hash tree的非叶子节点value的计算方法

是将该节点的所有子节点进行组合，然后对组合结果进行计算得出的Hash value。

例如下图就是一个Merkle Hash tree，那么节点7的Hash value必须是通过节点15和16的value计算而得。

Why use Merkle Hash tree？

目前在计算机领域，Merkle tree大多用来进行比对以及验证处理。在处理比对或验证的应用场景中，特别是在分布式环境下进行比对和验证处理时，

Merkle tree会大大减少数据的传输量和计算的复杂度。例如就拿图一举例，假如是15,16，...，30是一个个数据块的Hash值，我把这些数据从A传

到B，数据传输到B后，我想验证这些数据的有效性（B中收到的数据与A中的数据是否完全一致），只需要验证A，B上所构造的Merkle tree的root

节点的value是否一致即可，如果一致，则表明数据是有效的，在传输过程中没有发生变化。加入在传输过程中15对应的value值被篡改，则很容易

通过Merkle tree定位找到，因为此时节点0,1,3,7,15对应的值都发生了改变，定位的时间复杂度是O（log（n))。