上期我们学习了哈希指针，区块与区块之间通过哈希指针连接。今天我们将学习另一个用哈希指针建立的有用的数据结构——二叉树。使用哈希指针的二叉树也叫梅克尔树（Merkle trees），以发明者拉尔夫·梅克尔（Ralph Merkle）的名字命名。

梅克尔树结构

如图，我们来看梅克尔树的数据结构，所有的数据区块两两分组（如图的最底层），指向这些数据的哈希指针被储存在上一层的父节点（parent node）中，而这些父节点再次被两两分组，并且指向父节点的指针被储存在上一层的父节点中，一直持续这个过程，直到我们得一个单一的区块，即树根节点。

根据梅克尔树的数据结构，我们可以清楚的了解到，只要我们记住最前面的树根节点的哈希指针，我们就可以根据哈希指针回溯到表中的任意位置，这让我们能保证表中的数据不被篡改。如果有人篡改了梅克尔树底部的一些数据区块，会导致上一层的哈希指针不匹配，那么他不得不一直篡改上一层的哈希指针，直到数的顶端，而此刻，篡改即将终止，因为我们存储了树根节点的哈希指针。

因此，只要我们记住树根顶部的哈希指针，任何企图篡改数据的行为都会被检测到，这让数据篡改变得不可能实现。

隶属证明

梅克尔二叉树的另一个特点是就是它可以实现简洁的隶属证明。

对于任意一个需要被验证的数据块信息，只要我们知道该梅克尔树的根节点以及从该数据区块通向根节点的那些区块（忽略梅克尔树的其他部分），就可以完成该数据块是否隶属于梅克尔树。文字有些绕口，我们举个例子，再通过图解来验证下。首先我们已知根节点——Astar，现在有一位女神小倩，我们知道小倩在区块链实验室3年2班任教，那么小倩是否隶属于Astar呢。

我们来看验证过程，我们解密根节点Astar的哈希指针，发现有两个子节点——区块链实验室和区块链茶水室，于是我们继续解密子节点区块链实验室得到两个子节点3年1班和3年2班，我们根据提示路径继续解密3年2班，发现有两个子节点，一个就是我们要找的女神小倩，经过核对小倩就是我们要找的女神，他确实是隶属于Astar。这样就完成了整个隶属验证的过程。梅克尔树大概做的就是这样一个过程。

我们发现，如果整个梅克尔树上有n个节点，我们只需要展示约log（n）的项目，因为每个步骤只需要计算子区块的哈希值。

回顾下今天的内容，我们学习了哈希指针的另一个重要应用——梅克尔二叉树，加上上节课的区块结构，可以说哈希指针能应用在任何以指针为基础的数据结构中。在哈希指针构建的梅克尔二叉树中，我们可以有效地验证区块的隶属关系，同时方便计算。为分布式数据结构中，哈希指针和哈希运算可以说是常用的技巧，未来，在区块链技术的解密过程中，会反复提到。

文章原标题：侯震：有了二叉树，我终于知道我姑姑的女婿的小外甥是我什么人了  原作者：侯震