结构体数组在Ethereum的世界里，数据的最终存储形式是[(5)

上图来自wiki-MerkleTree，展示了一个简单的二叉哈希树。四个有效数据块L1-L4，分别被关联到一个叶子节点上。Hash0-0和Hash0-1分别等于数据块L1和L2的哈希值，而Hash0则等于Hash0-0和Hash0-1二者拼接成的新字符串的哈希值，依次类推，根节点的标签topHash等于Hash0和Hash1二者拼接成的新字符串的哈希值。

哈希树最主要的应用场景是p2p网络中的数据传输。因为p2p网络中可能存在未知数目的不可信数据源，所以确保下载到的数据正确可信并且无损坏无改动，就显得非常重要。哈希树可用来解决这个问题：每个待下载文件按照某种方式分割成若干小块后，组成类似上图的哈希树。首先从一个绝对可信的数据源获取该文件对应哈希树的根节点哈希值(top hash)，有了这个可靠的top hash后，就可以开始从整个p2p网络下载文件。不同的数据部分可以从不同的源下载，由于哈希树中任意的分支树都可以单独验证哈希值，所以一旦发现任何数据部分无法通过验证，都可以切换到其他数据源进行下载那部分数据。最终，完整下载文件所对应哈希树的top hash值，一定要与我们的可靠top hash相等。

Merkle-Patricia Trie(MPT)的实现

MPT是Ethereum自定义的Trie型数据结构。在代码中，trie.Trie结构体用来管理一个MPT结构，其中每个节点都是行为接口Node的实现类。下图是Trie结构体和node接口族的UML关系图：

在Trie结构体中，成员root始终作为整个MPT的根节点；originalRoot的作用是在创建Trie对象时承接入参hashNode；cacheGen是cache次数的计数器，每次Trie的变动提交后(写入的对象可由外部参数传入)，cacheGen自增1。Trie结构体提供包括对节点的插入、删除、更新，所有节点改动的提交(写入到传入参数)，以及返回整个MPT的哈希值。

node接口族担当整个MPT中的各种节点，node接口分四种实现: fullNode，shortNode，valueNode，hashNode，其中只有fullNode和shortNode可以带有子节点。

fullNode是一个可以携带多个子节点的父(枝)节点。它有一个容量为17的node数组成员变量Children，数组中前16个空位分别对应16进制(hex)下的0-9a-f，这样对于每个子节点，根据其key值16进制形式下的第一位的值，就可挂载到Children数组的某个位置，fullNode本身不再需要额外key变量；Children数组的第17位，留给该fullNode的数据部分。fullNode明显继承了原生trie的特点，而每个父节点最多拥有16个分支也包含了基于总体效率的考量。

shortNode是一个仅有一个子节点的父(枝)节点。它的成员变量Val指向一个子节点，而成员Key是一个任意长度的字符串(字节数组[]byte)。显然shortNode的设计体现了PatriciaTrie的特点，通过合并只有一个子节点的父节点和其子节点来缩短trie的深度，结果就是有些节点会有长度更长的key。

valueNode充当MPT的叶子节点。它其实是字节数组[]byte的一个别名，不带子节点。在使用中，valueNode就是所携带数据部分的RLP哈希值，长度32byte，数据的RLP编码值作为valueNode的匹配项存储在里。

这三种类型覆盖了一个普通Trie(也许是PatriciaTrie)的所有节点需求。任何一个[k,v]类型数据被插入一个MPT时，会以k字符串为路径沿着root向下延伸，在此次插入结束时首先成为一个valueNode，k会以自顶点root起到到该节点止的key path形式存在。但之后随着其他节点的不断插入和删除，根据MPT结构的要求，原有节点可能会变化成其他node实现类型，同时MPT中也会不断裂变或者合并出新的(父)节点。比如：

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-69032-5.html