在「Merkle Patricia Tree (MPT) 树详解之数据结构（一）」介绍了以太坊MPT树的结构，但是如何将MPT树持久化呢？以太坊采用LevelDB做数据库，如何将MPT树的节点映射成键值对存储到LevelDB呢？

以太坊的MPT树提供了三种不同的编码方式来满足不同场景的不同需求，三种编码方式为；

  • Raw编码（原生字符）
  • Hex编码（扩展16进制编码）
  • Hex-Prefix编码（16进制前缀编码）

三者的关系如下图所示，分别解决的是MPT对外提供接口的编码，在内存中的编码，和持久化到数据库中的编码。

Raw编码

MPT对外提供的API采用的就是Raw编码方式，这种编码方式不会对key进行修改，如果key是“foo”, value是”bar”，编码后的key就是[“f”, “o”, “o”]。

假设我们要把a作为key放入MPT树，key可以直接用a的ASCII表示97就可以了。

Hex编码

可以发现采用Raw编码以后，从a-z一共26个字母，如果采用分支节点（BranchNode）存储的话需要26个空间，如果再加上0-9一共10个数字和一个value，总共需要37个空间，以太坊的开发者权衡了一下觉得太多了，于是就改良了编码方式，有了Hex编码。

以太坊先定义了一个新单位nibble，一个nibble表示4个bit，0.5个byte。然后按照如下规则编码；

  • 将Raw输入的每个字符（1byte）拆分成2个nibble，前4位和后4位各一个nibble；
  • 将每个nibble扩展为1个byte（8个bit）；
  • 然后分别将Raw编码后的十六进制结果的每个b进行如下操作
    • b / 16；
    • b % 16；

有疑惑的话看一下这个例子就懂了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
a的ASCII编码为99（十进制），转换十六进制为63
采用Hex编码
[0] = 61 / 16 = 3
[1] = 61 % 16 = 13
编码后的结果 [3, 13]
在举个例子
输入"cat"，Raw编码后 [63, 61, 74]
63 / 16  = 3
63 % 16 = 15
61 / 16 = 3
61 % 16 = 13
74 / 16 = 4
74 % 16 = 10
编码后的结果 [3，15，3，13，4，10]

树的最后一位value是一个标识符，如果存储的是真实的数据项，即该节点是叶子节点，则在末尾添加一个ASCII值为16的字符作为终止标识符。添加后的结果是[3，15，3，13，4，10, 16]

采用Hex编码以后，可以看到原本需要的37个空间存储的消耗都被压缩到了17个空间，横向压缩，但是增加了纵向空间的消耗，是一种工程的妥协。根据Key的数量多少，压缩与否各有优劣。

HP编码（Hex-Prefix Encoding 16进制前缀编码）

前面介绍的Hex编码后的数据是在内存中的，如果要对Hex编码后的数据进行持久化，就会发现一个问题，我们对原数据进行了扩展，本来1个byte的数据被我们变成了2个byte，显然这对于存储来说是不可接受的，于是就又有了HP编码。

HP编码的过程如下；

  • 输入key（Hex编码的结果）如果有标识符，则去掉这个标识符。
  • key的头部填充一个nibble，填充的规则如下
    • 如果key的nibble长度是偶数则最后一位0
    • 如果key的nibble长度是奇数则最后一位1
    • 如果key是扩展节点则倒数第二位是0
    • 如果key是叶子节点则倒数第二位是1

例子：nibble长度是奇数的扩展节点填充为0001。

举个例子：

1
2
3
4
5
6
"cat"经过HP编码后的结果 [3，15，3，13，4，10, 16]
再用HP编码
1. 去掉16，同时表明这个是叶子节点。
2. 叶子节点，nibble数量是奇数个，这两个条件得出需要填充的值为 0010 0000
3. 将HP编码后的结果用二进制表示 [0010, 0000，0011, 1111, 0011, 1101, 0100, 1010]
4. 将HP编码后的结果合并成byte，为[00100000, 00111111, 00111101, 01001010]转换为十进制是[32, 63, 61, 74]

相较与cat的Raw编码，经过上面的Hex编码和HP编码，既可以能在内存中构建出MPT树，又可以尽可能减小存储所占用的空间，不得不说以太坊设计的巧妙。

安全的MPT

在上面介绍三种编码并没有解决一个问题，如果我们的key非常的长，会导致树非常的深，读写性能急剧的下降，如果有人不怀好意设计了一个独特的key甚至是可以起到DDOS攻击的作用，为了避免上面的问题，以太坊对key进行了一个特别的操作。

将所有的key都进行了一个keccak256(key)的操作，在「EVM深度分析之数据存储(二)」中也可以看到EVM持久化的数据也都进行了哈希操作，这样就可以避免上面问题的发生。

持久化MPT

MPT树节点Key的三种编码形式，但是这三种编码都是对key进行的操作，最终持久化到LevelDB中是k-v的形式，还需要对value进行处理。

在以太坊存储键值对之前会采用RLP编码对键值对进行转码，（RLP编码可以参照之前的文章「以太坊RLP编码」），将键值对编码后作为value，计算编码后数据的哈希（keccak256）作为key，存储在levelDB中。

在具体的实现中，为了避免出现相同的key，以太坊会给key增加一些前缀用作区分，比如合约中的MPT树，会增加合约地址，区块数据会增加表示区块的字符和区块号。
MPT树是以太坊非常非常核心的数据结构，在存储区块，交易，交易回执中都有用到，下图展示了MPT树的全貌，可以再感受一下MPT树的精巧

小结

其实随着数据的膨胀，LevelDB的读写速度都会变慢，这个是LevelDB实现导致的，目前也有一些针对性的优化。还有一种和MPT树非常相近的另一种数据结构BucketTree，也可以实现相同的功能，各有优劣。