以太坊存储数据的核心数据结构：MPT

点击上方“统一时代”订阅！

unitimes.io

全球视野，独到见解

作者| 欢乐酒吧

来源 | 简书

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 Tree，又称哈希树，中文名：Merkle Tree，主要用于数据集较大时的文件校验。 其主要特点是：

解释：

1、在最底层，和hash list一样，我们把数据分成小的数据块，有对应的hash与之对应；

2、往上不是直接计算根哈希，而是将相邻的两个哈希组合成一个字符串，然后计算这个字符串的哈希，这样每两个哈希就会结婚生子。 获得“subhash”。 如果底层的哈希总数是奇异的，那么末尾一定只有一个哈希。 这样的话，直接对它进行hash操作，所以也可以得到它的sub-hash再往上推，还是一样的，可以得到数量更少的新一级的hash，

3.最后一定要形成一棵倒挂的树。 在树根的这个位置，这一代只剩下一个根哈希，我们称之为Merkle Root。

对于这种数据结构，在实际应用中会有哪些应用场景呢？ 比如我们知道从网上下载的文件大部分都是P2P下载的。 这些文件将被分成许多小数据块。 每个数据块都是从不同的来源下载的，这些机器可以被认为是不稳定的或不可信的。 下载文件后，我们需要验证文件的完整性。 这时候我们就不能再对文件进行划分，计算它的Hash和下载之前的Hash进行比较，这时就需要用到Merkle Tree了。

下载前，先从可靠来源获取文件的默克尔树根。 下载后，在合并文件之前比较小文件的Hash。 如果它们相同，则认为是可靠的。 如果没有，则确定该文件已损坏。 ，从新的源重新下载，文件合并后，计算小数据块的Hash最后计算根Hash，也成为Merkle Root，然后比较根Hash是否一致。 这样就避免了对整个文件进行Hash计算，因为在文件过大的时候这种计算是比较耗时的。

帕特里夏树

Patricia树，或Patricia trie，或crit bit tree，压缩前缀树，是一种比较节省空间的Trie。 对于基数树的每个节点，如果该节点是唯一的子节点，则将其与父节点合并。

MPT（默克尔帕特里夏树）

上面我们介绍了Merkle Tree和Patricia Tree，而MPT（Merkle Patricia Tree）顾名思义就是两者的结合。 MTP树种的节点包括空节点、叶节点、扩展节点和分支节点。

Nibble：是密钥的基本单位，是一个四元组（四位的组合，比如0010用二进制表示就是一个四元组）

**Empty节点****：简单的表示empty，在代码中就是一个空字符串。

叶子节点（leaf）：只有key和value两个元素，表示为[key, value]的键值对，其中key是key的特殊十六进制编码，value是value的RLP编码。

扩展节点（extension）：也是[key,value]的键值对，但是这里的value是其他节点的hash值，这个hash可以用来查询数据库中的节点。 也就是说，通过hash链接到其他节点。

分支节点（branch）：分支节点有17个元素。 回到Nibble，四元组是key的基本单位，四元组最多有16个值。 所以前16个在其遍历中一定落入key的16个可能的半字节值中的每一个。 第17个是存放那些以当前节点结束的节点（比如有3个key，分别是(abc, abd, ab)第17个字段存放的是ab节点的值）

还有一些知识点需要了解。 为了将MPT树存入数据库，从数据库中恢复MPT树，对Extension和Leaf的节点类型做了特殊定义：如果是extension节点，那么前缀为0，而这个在密钥前面添加 0。 如果是叶子节点遍历以太坊节点，则前缀为1。 同时，还为密钥的长度设置了校验类型。 如果是奇数长度，则标记为1，如果是偶数长度遍历以太坊节点，则标记为0。

以太坊的每个区块头不仅包含一棵 MPT 树，而是三棵 MPT 树，分别对应四种对象：

区块头中的 State Trie 状态树

Transactions Trie 区块头中的交易树

Receipts Trie 区块头中的收据树

Storage Trie 存储树

MPT树种还有一个重要的概念：一种特殊的十六进制前缀（hex-prefix，HP）编码来对密钥进行编码。 我们先了解一下编码定义规则：

HEX-Prefix 十六进制前缀编码

官方有一个详细结构的例子：