一文读懂以太坊存储数据核心数据结构：MPT
作者 | JouyPub
出品 | 区块链大本营
MPT (Merkle Patricia Tries) 是以太坊存储数据的核心数据结构，它是由 Merkle Tree 和 Patricia Tree 结合的一种树形结构，理解 MPT 有助于我们更好的理解以太坊的数据存储。
在了解 MPT 数据结构之前，我们需要先来看看基本的 Tree 结构和 Merkle Tree、Patricia Tree。
Trie 字典树
Trie 树，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。
上图是一棵 Trie 树，表示了字符串集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} ，从上图中我们可以看出Trie树的特点：
- 根节点不包含字符，除根节点外的每一个子节点都包含一个字符。
- 从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
- 每个节点的所有子节点包含的字符互不相同。
但是从上面的结构也可以看出一个问题：高度不可控，如下图所示。所以就有了 Patricia 树 (压缩前缀树)，后面会介绍到。
Merkle树
Merkle树，也被称为 Hash Tree，中文名称：默克尔树，主要用于数据集较大时的文件校验。其主要特点为：
- 叶节点存储着数据块的 Hash（如：文件块、一段数据集）
- 非叶子节点 (包括中间节点和根节点) 存储着对应子节点 Hash 值串联字符串之后的 Hash 值。
从上图中可以看出：
- 在最底层，和哈希列表一样，我们把数据分成小的数据块，有相应地哈希和它对应；
- 往上走，并不是直接去运算根哈希，而是把相邻的两个哈希合并成一个字符串，然后运算这个字符串的哈希，这样每两个哈希就结婚生子，得到了一个”子哈希“。如果最底层的哈希总数是单数，那到最后必然出现一个单身哈希，这种情况就直接对它进行哈希运算，所以也能得到它的子哈希再往上推，依然是一样的方式，可以得到数目更少的新一级哈希；
- 最终必然形成一棵倒挂的树，到了树根的这个位置，这一代就剩下一个根哈希了，我们把它叫做 Merkle Root。
对于这种数据结构，在实际应用中会有哪些应用场景了。
举个例子，我们知道现在从网上下载文件，很多都是 P2P 下载，文件会切分成很多小的数据块，每个数据块从不同的来源上下载，这些机器可以认为是不稳定或不可信的，文件下载完之后我们需要校验文件的完整性，这时我们总不能把文件再次切分然后分别计算它的 Hash 和下载前的 Hash 做对比吧，这时就需要用到 Merkle Tree。
在下载前，先从可靠的源获得文件的 Merkle Tree 树根。下载后，在合并文件之前先对比小文件的Hash是否一样，如果一样就认为是可靠的，如果不一样，就判定文件被损坏，从新的来源重新下载。
文件合并之后，计算小数据块的 Hash 并最终计算根 Hash，也成为 Merkle Root，然后对比根 Hash 是否一致。这样就避免了对整个文件进行 Hash 计算，因为当文件太大时，这种计算是很耗时。
Patricia树
Patricia 树，或称 Patricia trie，或 crit bit tree，压缩前缀树，是一种更节省空间的 Trie。对于基数树的每个节点，如果该节点是唯一的儿子的话，就和父节点合并。
MPT (Merkle Patricia Tree)
上面我们介绍了Merkle Tree和Patricia Tree，而MPT（Merkle Patricia Tree），顾名思义就是这两者的结合。MTP树种的节点包含空节点、叶子节点、扩展节点和分支节点。
Nibble：它是 key 的基本单元，是一个四元组（四个bit位的组合例如二进制表达的 0010 就是一个四元组）
**空节点****：简单的表示空，在代码中是一个空串。
叶子节点 (leaf)：只有两个元素，分别为key和value，表示为[key,value]的一个键值对，其中key是key的一种特殊十六进制编码，value是value的RLP编码。
扩展节点 (extension)：也是 [key，value] 的一个键值对，但是这里的value是其他节点的hash值，这个hash可以被用来查询数据库中的节点。也就是说通过hash链接到其他节点。
分支节点 (branch)：分支节点有17个元素，回到 Nibble，四元组是 key 的基本单元，四元组最多有16个值。所以前16个必将落入到在其遍历中的键的十六个可能的半字节值中的每一个。第17个是存储那些在当前结点结束了的节点(例如， 有三个 key,分别是 (abc ,abd, ab) 第17个字段储存了ab节点的值)
这里还有一些知识点需要了解的，为了将 MPT 树存储到数据库中，同时还可以把MPT树从数据库中恢复出来，对于 Extension 和 Leaf 的节点类型做了特殊的定义：如果是一个扩展节点，那么前缀为0，这个0加在 key 前面。如果是一个叶子节点，那么前缀就是1。
同时对 key 的长度就奇偶类型也做了设定，如果是奇数长度则标示1，如果是偶数长度则标示0。
以太坊的每一个区块头，并非只包含一棵 MPT 树，而是包含了三棵 MPT 树，分别对应了四种对象：
State Trie 区块头中的状态树
- key => sha3(以太坊账户地址address)
- value => rlp(账号内容信息account)
Transactions Trie 区块头中的交易树
- key => rlp(交易的偏移量 transaction index)
- 每个块都有各自的交易树，且不可更改
Receipts Trie 区块头中的收据树
- key = rlp(交易的偏移量 transaction index)
- 每个块都有各自的交易树，且不可更改
Storage Trie 存储树
- 存储只能合约状态
- 每个账号有自己的Storage Trie
MPT树种还有一个重要的概念：特殊的十六进制前缀(hex-prefix, HP)编码来对key编码，我们先来了解一下编码定义规则：
- RAW 原始编码，对输入不做任何变更
- HEX 十六进制编码：a）RAW编码输入的每个字符分解为高4位和低4位。比如key=>"bob",b的ASCII十六进制编码为0x62，o的ASCII十六进制编码为0x6f，分解成高四位和第四位，16表示终结 0x10，最终编码结果为[6 2 6 15 6 2 16]；b）如果是叶子节点，则在最后加上Hex值0x10表示结束；c）如果是分支节点不附加任何Hex值。
HEX-Prefix 十六进制前缀编码：
- 输入key结尾为0x10，则去掉这个终止符
- key之前补一个四元组这个Byte第0位区分奇偶信息，第1位区分节点类型
- 如果输入key的长度是偶数，则再添加一个四元组0x0在flag四元组后
- 将原来的key内容压缩，将分离的两个byte以高四位低四位进行合并
- 十六进制前缀编码相当于一个逆向的过程，比如输入的是[6 2 6 15 6 2 16]，根据第一个规则去掉终止符16。根据第二个规则key前补一个四元组，从右往左第一位为1表示叶子节点，从右往左第0位如果后面key的长度为偶数设置为0，奇数长度设置为1，那么四元组0010就是2。根据第三个规则，添加一个全0的补在后面，那么就是20.根据第三个规则内容压缩合并，那么结果就是[0x20 0x62 0x6f 0x62]
官方有一个详细的结构的示例：
怎么样，看了这篇文章，对MPT和树状结构有基本的了解了吗？未来，营长将奉上更多优质的技术普及文章，敬请期待！
推荐阅读：