默克尔帕特里夏树（Merkle Patricia Tree）简称MPT树，MPT树结合了字典树和默克尔树的优点，在压缩字典树中根节点是空的，而MPT树可以在根节点保存整棵树的哈希校验和，而校验和的生成则是采用了和默克尔树生成一致的方式。
以太坊采用MPT树来保存，交易，收据以及世界状态，为了压缩整体的树高，降低操作的复杂度，以太坊又对MPT树进行了一些工程上的优化。将树节点分成了四种；
- 空节点（hashNode）
- 叶子节点（valueNode）
- 分支节点（fullNode）
- 扩展节点（shortNode）
通过以太坊黄皮书中很经典的一张图，来了解不同节点的具体结构和作用
可以看到有四个状态要存储在世界状态的MPT树中，需要存入的值是键值对的形式。自顶向下，我们首先看到的keccak256生成的根哈希，参考默克尔树的Top Hash，其次看到的是绿色的扩展节点Extension Node，其中共同前缀shared nibble是a7，采用了压缩前缀树的方式进行了合并，接着看到蓝色的分支节点Branch Node，其中有表示十六进制的字符和一个value，最后的value是fullnode的数据部分，最后看到紫色的叶子节点leadfNode用来存储具体的数据，它同样对路径进行了压缩。
以太坊的智能合约为例，智能合约部署成功后会得到一个地址，比如是0xa16de3199ca3ee1bc1e0926d53c12ffacdf3f2c4，除去开头的0x表示这是一个十六进制的字符串的标识，把其余字符按照压缩前缀树的规则存入MPT树，键（Key）就是合约的地址，键对应的值（Value）就是合约账户的信息，其中有合约代码和合约状态。合约中的状态变量又会做为一个键值对存入合约每个合约自己的MPT树中。相当于合约自己的MPT树又通过一个MPT树来进行组织。如果账户是外部账户，没有合约代码和合约状态，就直接存储了账户余额。而组织这一切的MPT树就叫世界状态树。世界状态树只需要存储每个合约状态树的根哈希，当合约状态变更，合约状态树的根哈希发生变化，传导到世界状态树，世界状态树的根哈希发生变化，从而让外部感知到世界状态发生了修改。
在之前讲解EVM的章节中可以看到需要持久化的数据都是以键值对的形式存在的，而键是由keccak256这个函数计算得到，用十六进制表示后刚好对应MPT 树中分支节点的0-f的16个分支。
最终的数据还是以键值对的形式存储在LevelDB中的，MPT树相当于提供了一个缓存，帮助我们快速找到需要的数据。
在Go实现的以太坊中，MPT树最终是存储在LevelDB数据库中的，LevelDB是Google开源的持久化KV单机数据库，具有很高的随机写，顺序读/写性能。以太坊通过对叶子节点按照一定的编码规则编码后存入LevelDB。
以太坊的MPT树提供了三种不同的编码方式来满足不同场景的不同需求，三种编码方式为；
- Raw编码（原生字符）
- Hex编码（扩展16进制编码）
- Hex-Prefix编码（16进制前缀编码）
三者的关系如下图所示，分别解决的是MPT对外提供接口的编码，在内存中的编码，和持久化到数据库中的编码。
MPT对外提供的API采用的就是Raw编码方式，这种编码方式不会对key进行修改，如果key是“foo”, value是"bar"，编码后的key就是["f", "o", "o"]。
假设我们要把a作为key放入MPT树，key可以直接用a的ASCII表示97就可以了。
可以发现采用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；
有疑惑的话看一下这个例子就懂了
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的数量多少，压缩与否各有优劣。
前面介绍的Hex编码后的数据是在内存中的，如果要对Hex编码后的数据进行持久化，就会发现一个问题，我们对原数据进行了扩展，本来1个byte的数据被我们变成了2个byte，显然这对于存储来说是不可接受的，于是就又有了HP编码。
HP编码的过程如下；
- 输入key（Hex编码的结果）如果有标识符，则去掉这个标识符。
- key的头部填充一个nibble，填充的规则如下
- 如果key的nibble长度是偶数则最后一位0
- 如果key的nibble长度是奇数则最后一位1
- 如果key是
扩展节点则倒数第二位是0 - 如果key是
叶子节点则倒数第二位是1
例子：nibble长度是奇数的扩展节点填充为0001。
举个例子：
"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树，又可以尽可能减小存储所占用的空间，不得不说以太坊设计的巧妙。
在上面介绍三种编码并没有解决一个问题，如果我们的key非常的长，会导致树非常的深，读写性能急剧的下降，如果有人不怀好意设计了一个独特的key甚至是可以起到DDOS攻击的作用，为了避免上面的问题，以太坊对key进行了一个特别的操作。
将所有的key都进行了一个keccak256(key)的操作，这样就保证了所有key的长度都为一致定长。
MPT树节点Key的三种编码形式，但是这三种编码都是对key进行的操作，最终持久化到LevelDB中是k-v的形式，还需要对value进行处理。
在以太坊存储键值对之前会采用RLP编码对键值对进行转码，将键值对编码后作为value，计算编码后数据的哈希（keccak256）作为key，存储在levelDB中。
在具体的实现中，为了避免出现相同的key，以太坊会给key增加一些前缀用作区分，比如合约中的MPT树，会增加合约地址，区块数据会增加表示区块的字符和区块号。 MPT树是以太坊非常非常核心的数据结构，在存储区块，交易，交易回执中都有用到，下图展示了MPT树的全貌，可以再感受一下MPT树的精巧。
其实随着数据的膨胀，LevelDB本身的读写速度都会变慢，这个是LevelDB实现导致的，这个也是制约MPT树性能的重要因素。
以太坊区块中有三颗MPT树，分别是状态树，交易树，收据树 ，分别存储了以太坊中的世界状态，本区块的交易，本区块的交易回执，其中交易和交易回执是一一对应的。
当以太坊每次执行一笔交易的时候，以太坊对应的世界状态都会发生改变。以太坊作为一个公链平台，上面有大量合约所对应的海量状态，如果每次发生状态改变都重建状态树无疑会消耗巨大的计算资源。为了解决这个问题，以太坊提出了增量修改状态树的方法。每次以太坊状态发生改变后并不会去修改原来的MPT树，而是会新建一些分支，如下图所示；
以太坊每次状态发生改变后，只会影响到世界状态MPT树的少量节点，新生成的世界状态树只需要重新计算受到影响的少量节点和与之相连节点的哈希即可。
以太坊的状态非常适用于用MPT树来存储，MPT树的特点与以太坊状态的特点非常契合，当采用MPT树存储以太坊状态以后可以带来如下的优势；
- 当一个账户的余额发生改变后，对应路径的哈希也发生了变化，然后自底而上的更新对应路径上的哈希值，直至Satet Root，这样可以计算最少的哈希次数。
- 以太坊中的全节点维护的是增量的MPT状态树，因为每次一个区块对世界状态的修改都只是很小的一部分，增量修改既有利于区块回滚，又可以节约开销。
- 在以太坊中区块临时分叉很普遍，但是由于以太坊智能合约的复杂性，如果不记录原始状态，很难根据合约代码回滚状态。
以太坊在智能合约执行时会产生一个交易回执（Receipt）记录了此笔交易的执行结果，交易信息和区块信息。
当查询轻节点查询通过布隆过滤器找到交易后，为了避免误识，还会再次查询回执来避免误识。
交易树的作用是提供了交易的默克尔证明，证明某个交易被打包到某个区块里，轻节点不用存储区块体仅根据提供的默克尔证明就可以快速判断交易是否已经被打包。
交易树和收据树只依赖当前的区块，而状态树是把链上所有状态都包含进去，交易树和收据树是独立的，状态树会共享树的节点。
为什么状态树要包含所有链上所有的状态呢？
举个例子，当一笔转账操作的发起时，需要判断发起账户是否有足够的ETH来完成这笔转账，这个时候要通过查找状态树查看对应账户的状态，但是如果为了节约空间，只保存了当前区块账户的状态，就需要逐块查找，非常影响性能，甚至这个转账交易的发起者都不存