前言

MPT树，全称Merkle Patria Tree，是以太坊采用的一种经典存储结构。该结构不仅仅被以太坊所使用，像国内金链盟的Fisco Bcos联盟链就将该结构纳入了自身的存储体系。MPT树的概念可以说是很简单，就是merkle + trie，但又因为它是这些知识的综合体，故往往又弄的初学者一头雾水。这里采用一种层层递进的方式将这个MPT树的概念讲清楚。

本质

MPT树，本质就是一个Key Value字典，就是这么简单。在以太坊中，这个字典可用于存储账户信息，其中Key表示账户地址，Value表示账户信息，例如余额。 假设我们有如下账户数据：

{
"ada.wu": 30,
"ada.li": 40,
"bob":50,
"boris":60
} 

我们来看如何一步一步的用MPT树来实现相应的存储。为了更有亲切感，图都由我来手绘。

字典树

字典的最经典实现方式当然就是HashMap了，但除此之外，还有一种借助“字典树”的方案, 下图就是字典树的方式来实现上述存储：

这种方案的好处显然是节省了存储空间，因为公共数据只存储一份。比如ada.wong和ada.zhang就共享了同一个前缀ada。而且查询的效率仅取决于树高，即Key的长度。

压缩

上图中，树还是太高了些，实际上MPT树对常规的字典树做了优化，仅在必要的地方将节点分裂。下图是不是就舒服多了：

由于树高被压缩了不少，查询开销也就被大幅度降低。

Merkle化

在上述字典树的基础上，我们来对它做一番自底向上的merkle化操作。
所谓merkle化操作，就是按照如下规则自底向上地生成哈希值：

• 如果是叶子节点，那么H(leaf) = H(leaf.Value)。
• 如果是非叶节点，那么H(leaf) = H( H(child1) + H(child2) + .. + H(childN))
  其中H表示哈希操作。

在本例中，merkle化的示意图如下。最终根节点的哈希值是F。

这个merkle过程有什么神奇的地方呢？神奇之处在于，如果任何一个叶子节点的值发生变动，那么该节点的哈希值也会更改，而由于父节点的哈希值依赖于该节点的哈希值，故而父节点的哈希值也会更改，这样一路传导上去，最终根节点也会被更改。理解了这一点是理解MPT树的关键。实际上，一个MPT树的根节点的哈希值（简称为merkle root）唯一的刻画了这棵树，可以看作是这棵字典树本身的指纹。

以上，就构造好了一棵MPT树，回头再来看MPT树的概念是不是就很容易理解了，实际就是merkle + trie。但是它是在以太坊中怎么用的呢，特别是根节点的哈希值，有什么用？见下文。

MPT树在区块链中的应用

MPT State

随着account数据的改变，account的hash也进行改变。于此同时，MPT的根的hash也会改变。
不同的时候，account的数据不同，对应的MPT的根就不同。
此处，以太坊把这层含义进行了具体化，提出了“状态”的概念。
把MPT根的hash，叫state root。
state root是区块中的一个字段，每个区块对应着不同的“状态”。区块中的交易会对account进行操作，进而改变account中的数据。不同的区块下，account的数据有所不同，即此区块的状态有所不同，具体的，是state root不同。从某个区块中取出这个区块的state root，查询到MPT的根节点，就能索引到这个区块当时account的数据历史。

每次生成一个新的区块，以太坊状态发生改变后并不会去修改原来的MPT树，而是会新建一些分支，如下图所示：

• 当一个账户的余额发生改变后，对应路径的哈希也发生了变化，然后自底而上的更新对应路径上的哈希值，直至Satet Root，这样可以计算最少的哈希次数。
• 以太坊中的全节点维护的是增量的MPT状态树，因为每次一个区块对世界状态的修改都只是很小的一部分，增量修改既有利于区块回滚，又可以节约开销。
• 在以太坊中区块临时分叉很普遍，但是由于以太坊智能合约的复杂性，如果不记录原始状态，很难根据合约代码回滚状态。

以上，就是对MPT树的介绍，希望能给大家讲清楚。