以太坊采用基于账户的模式，系统中显式记录每个账户的余额。而以太坊这样一个大型分布式系统中，是采用的什么样的数据结构来实现对这些数据的管理的。
首先，==我们要实现从账户地址到账户状态的映射==。在以太坊中，账户地址为 160 位，表示为 40 个 16 进制数。状态包含了余额 (balance)、交易次数 (nonce),合约账户中还包含了code (代码)、存储 (stroge)。
直观地来看，其本质上为 Key-value 键值对，所以直观想法便用哈希表实现。若不考虑哈希碰撞，查询直接为常数级别的查询效率。但采用哈希表，难以提供 merkle proof。
如何组织账户的数据结构？
-
我们能否像 BTC 中，将哈希表的内容组织为 Merkle Tree？
==当新区块发布，哈希表内容会改变，需要再次将其组织为新的 Merkle Tree。如果这样，每当产生新区块（ETH 中新区块产生时间为 10s 左右），都要重新组织 Merkle Tree，很明显这是不现实的==。
需要注意的是，比特币系统中没有账户概念，交易由区块管理，而区块包含上限为 4000 个交易左右，所以 Merkle Tree 不是无限增大的。而 ETH 中，Merkle Tree 来组织账户信息，很明显其会越来越庞大。
实际中，发生变化的仅仅为很少一部分数据，我们每次重新构建 Merkle Tree 代价很大
-
那我们不要哈希表了，直接使用 Merkle Tree，每次修改只需要修改其中一部分即可，这个可以吗？
实际中，Merkle Tree 并未提供一个高效的查找和更新的方案。此外，==将所有账户构建为一个大的 Merkle Tree，为了保证所有节点的一致性和查找速度，必须进行排序==。
-
那么经过排序，使用 Sorted Merkle Tree 可以吗？
新增账户，由于其地址随机，插入 Merkle Tree 时候很大可能在 Tree 中间，发现其必须进行重构。所以 Sorted Merkle Tree 插入、删除(实际上可以不删除)的代价太大。
Tips:
BTC 系统中，虽然每个节点构建的 Merkle Tree 不一致（不排序），但最终是获得记账权的节点的 Merkle Tree 才是有效的，因此不需要每个节点构建一致的 Merkle Tree。
既然哈希表和 Merkle Tree 都不可以，那么我们看一下实际中以太坊采取的数据结构：MPT。
特点：
- trie 中每个节点的分支数目取决于 Key 值中每个元素的取值范围（图例中最多 26 个英文字母分叉和一个结束标志位）
- trie 查找效率取决于 key 的长度。实际应用中（以太坊地址长度为 160 bit）
- 理论上哈希会出现碰撞，而 trie 不会发生碰撞
- 给定输入，无论如何顺序插入，构造的 trie 都是一样的
- 更新操作局部性较好
缺点：
- trie 的存储浪费。很多节点只存储一个 key，但其“儿子”只有一个，过于浪费。因此，为了解决这一问题，我们引入 Patricia tree/trie
需要注意的是，如果新插入单词，原本压缩的路径可能需要扩展开来。那么，需要考虑什么情况下路径压缩效果较好？==树中插入的键值分布较为稀疏的情况下，路径压缩效果较好==。
在以太坊系统中，160 位的地址存在 2^160 种，该数实际上已经非常大了，和账户数目相比，可以认为地址这一键值非常稀疏。
因此，我们可以在以太坊账户管理种使用 Patricia tree 这一数据结构！但实际上，在以太坊种使用的并非简单的 PT(Patricia tree)，而是 MPT(Merkle Patricia tree)。
以太坊中将所有账户组织为一个经过路径压缩和排序的 Merkle Tree，其根哈希值存储于 block header 中。BTC 中只有一个交易组成的 Merkle Tree，而以太坊中有三个。也就是说，在以太坊的 block header 中，存在有三个根哈希值。
根哈希值的用处：
- 防止篡改
- 提供 Merkle proof，可以证明账户余额，轻节点可以进行验证
- 证明某个发生了交易的账户是否存在
以太坊中针对 MPT(==Merkle Patricia tree==) 进行了修改，我们称其为 MPT(Modified Patricia tree)。
下图为以太坊中使用的 MPT 结构示意图，右上角表示四个账户（为直观，显示较少）和其状态（只显示账户余额）。（==需要注意这里的指针都是哈希指针==）
每次发布新区块，状态树中部分节点状态会改变。但改变并非在原地修改，而是新建一些分支，保留原本状态。如下图中，==仅仅有新发生改变的节点才需要修改，其他未修改节点直接指向前一个区块中的对应节点==。（其中 state root 为状态树的根 hash 值。）
所以，系统中全节点并非维护一棵 MPT，而是每次发布新区块都要新建 MPT。只不过大部分节点共享。
为什么要保存原本状态？为何不直接修改？
为了便于回滚。如下 1 中产生分叉，而后上面节点胜出，变为 2 中状态。那么，下面节点中状态的修改便需要进行回滚。因此，需要维护这些历史记录。
比特币中的交易比较简单，比如转账交易，回滚比较容易；以太坊中有智能合约，可以实现很复杂的功能，无法推算出执行前的状态，所以必须保存之前的状态。
- block header 中的数据结构
-
区块结构
-
区块在网上真正发布时的信息
状态树中保存 Key-value 对，key 就是地址，而 value 状态通过 RLP(Recursive Length Prefix，一种进行序列化的方法) 编码序列号之后再进行存储。