cc 当你想要了解区块链技术时，梅克尔树总是绕不开的话题。梅克尔树作为区块链的基本组成部分，在其中承担着不可取代的作用。下面我们就通过本文来一起了解一下梅克尔树。
梅克尔树简介
梅克尔树因为名为Merkle trees，又叫哈希树，简单来说就是区块链中存储hash值的一种树状型机构，它由一个根节点、一组中间节点和一组叶节点组成。最下面的叶节点包含存储数据或其哈希值，每个中间节点是它的两个孩子节点内容的哈希值，根节点也是由它的两个子节点内容的哈希值组成。
梅克尔树的原理
梅克尔树通常包含区块体的底层数据库， 区块头的根哈希值 (即Merkle根) 以及所有沿底层区块数据到根哈希的分支。梅克尔树运算过程一般是将区块体的数据进行分组哈希， 并将生成的新哈希值插入到梅克尔树中，如此递归直到只剩最后一个根哈希值并记为区块头的Merkle根。
最常见的梅克尔树是比特币采用的二叉梅克尔树,，其每个哈希节点总是包含两个相邻的数据块或其哈希值。其特点如下：
- 梅克尔树是一种树，大多数是二叉树，也可以多叉树，无论是几叉树，它都具有树结构的所有特点；
- Merkle Tree的叶子节点的value是数据集合的单元数据或者单元数据hash。
- 非叶子节点的value是根据它下面所有的叶子节点值，然后按照Hash算法计算而得出的。
梅克尔树的作用
梅克尔树大多用来进行完整性验证。比如分布式环境下，从多台主机获取数据，怎么验证获取的数据是否正确呢，只要验证梅克尔树根哈希一致即可。
梅克尔树还可以用来对数据进行快速比对，快速定位到不一致的数据。比如分布式存储中，一份数据会有多个副本，并且分布在不同的机器上。为了保持数据一致性，需要进行副本同步。如果采用直接传输数据进行比对，非常低效，所以一般采用对数据进行哈希，传输哈希值进行对比的方法。因此，可以对每台机器需要比对的数据构造梅克尔树，如果根哈希一致，则数据相同，如果根哈希不一致，则通过梅克尔树快速检索到不一致的数据。
梅克尔树的种类
即根哈希（root hash）
梅克尔树最为常见和最简单的形式，是二进制梅克尔树（ binary Mekle tree），其中一bucket单位的数据块总是包含了两个相邻的块或哈希。哈希算法允许了一个整齐的机制，被称之为梅克尔证明（Merkle proofs）。一个梅克尔证明包含了一个数据块，这颗梅克尔树的根哈希，以及包含了所有沿数据块到根路径哈希的“分支”。
帕特里夏树
以太坊所使用的梅克尔树，被称为“梅克尔.帕特里夏树”（Merkle Patricia tree）。其工作原理，最为简单的解释是，一个以编码形式存储到记录树的“路径”的值。每个节点会有16个子（children），所以路径是由十六进制编码来确定的。
梅克尔树的优点
- 梅克尔树极大地提高了区块链的运行效率和可扩展性，使得区块头只需包含根哈希值而不必封装所有底层数据，这使得哈希运算可以高效地运行在智能手机甚至物联网设备上；
- 梅克尔树可支持 “简化支付验证” 协议，即在不运行完整区块链网络节点的情况下，也能够对（交易）数据进行检验。
免责声明：素材源于网络，如有侵权，请联系删稿。
