以太坊的状态树 #
上一篇文章中我们说了每个以太坊账户中有余额、nonce、code、storage等属性，这篇文章就是讲用什么数据结构，将用户地址与这些属性关联起来。简单来说就是如何存储 address -> state 映射关系。首先要明确这个数据结构需要实现的目的：
- 给手机钱包等轻节点提供Merkle Proof验证，能够验证任意用户的状态。
- 保证账户状态的防篡改与可验证性，任意微小的改变都能被感知。
- 适配以太坊的状态模型与性能需求，以高效快捷的方式在各节点之前同步及验证状态。
方案1: 哈希表 #
既然是映射，一个直观的想法是哈希表，即系统中的全节点维护一个哈希表，查询与操作的时间复杂度都是O(1)，简单又高效。但是缺点也很明显，哈希表没法提供地址状态的Merkle Proof。
方案2: Merkle Tree #
既然要满足Merkle Proof，那能Merkle Tree就天然地满足了这个需求，能跟比特币一样否直接使用Merkle Tree？答案是NO。
为什么比特币中能使用Merkle Proof，而以太坊不行呢？是因为比特币中用Merkle Tree存储的是一个区块的交易数据，前面我们分析过大概是4000个交易。而以太坊需要存储的是所有用户的状态数据，这里可能是千万量级的，如果每次发布区块都要重新构建这个Merkle Tree，从效率上来说并不可行，实际上每次发布区块只涉及部分地址的状态变更，从这点来看重建Merkle Tree的性价比也太低了。
另外，每个节点打包时虽然状态一样，但是只要叶子节点顺序不一致，那Merkle Tree的根哈希值也不一样，无法做到节点之间同步。
如上图所示，虽然两个节点打包的都是ABCD四个账户的状态数据，但最后他们的根哈希值并不相同。
那如果强制要求Merkle Tree的叶子节点有序，即Sorted Merkle Tree呢？
Sorted Merkle Tree虽然能解决根哈希值不同的问题，但当新账户加入时，同样有部分的Merkle Tree需要重建。例如新增账户B’，B’右侧的的Merkle Tree需要重建。
方案3: Merkle Patricia Tree #
以太坊中实际使用的数据结构叫Merkle Patricia Tree简称MPT，其由压缩的Merkle Tree + Trie Tree组成 。在讲MPT之前，先讲如果用Trie Tree，即前缀树来实现会怎么样。
Trie Tree #
有词根相近的五个单词General、Genesis、Go、God、Good，他们在Trie Tree中的存储如下所示，这五个单词长度是不同的，导致每个单词的查找效率不同，长度越长，查找效率越低。
如果我们将所有以太坊的账户地址组成一颗Trie Tree，则这颗树具有以下特点：
- 查找效率一致，因为以太坊账户长度都是固定的，由40个16进制的数组成
- 不会产生哈希碰撞
- 给定的地址，无论插入顺序如何，其最终结构都不会改变
- 更新友好，只需更新树特定的路径，不会像Merkle Tree一样牵一发而动全身
Patricia Trie #
Trie Tree解决了Merkle Tree的一些痛点，但其本身也有一个缺陷，就是存储浪费问题。如下图，General可以说是一脉单传的，会造成存储空间的浪费且查询效率较低。
如果将其压缩一下，就变成了Patricia Trie，即压缩前缀树，其即节省了存储空间，也大大地提升了查询效率。因为以太坊的账户地址是40个16进制的数组成，本身是足够稀疏的，所以这种数据结构又提高了查询的账户的查询效率。
Merkle Patricia Trie #
有了前面的铺垫，以太坊的数据结构MPT已经呼之欲出了，我们把Patricia Trie的普通指针换成哈希指针，再计算出一个根哈希值，就是Merkle Patricia Trie了，其兼具了Merkle Tree与Patricia Trie的特点。在以太坊中一个区块有状态树、交易树、收据树三个MPT，后面两种我们下一篇再讲。
我们再来看看MPT是如何满足我们一开始提到的三个目的：
- Merkle Proof验证：与比特币一样，全节点提供一条Proof路径及根哈希值，轻节点根据路径计算出根哈希值，对比两个根哈希值是否相同。
- 防篡改：Merkle Tree的基础属性，状态变更会导致整颗树变更。
- 高性能：插入新地址，只需要更新当前地址涉及的路径的哈希值即可。
新区块的发布 #
以太坊中用户状态不能直接在本地修改，核心原因是为了保证区块链的去中心化共识、状态可验证性和历史可追溯性，本地直接修改会破坏全网状态的一致性与安全性
如图所示，新的区块中大部分数据是跟前一个区块共享的，只有新的变更会另外创建一个分支。为什么不能直接在本地修改呢？在以太坊中如果两个新区块出现导致分叉，如果某个区块胜出成为最长合法链，那另外一个区块需要回滚到前一个区块，再继续沿着最长合法链往下挖，直接在本地修改，那这个区块根本就无法回滚，因为他前一个区块的历史数据早就被覆盖了。还有一个原因是以太坊需要保留所有历史状态以支持审计、智能合约溯源和链上数据分析，本地直接修改会抹除历史数据，违背区块链 “不可篡改” 的核心特性。