以太坊采用的是基于账户的模式，系统显式地维护每个账户的余额

功能：

账户地址到账户状态的映射 address=>state

        (160bits=20字节=>40个16进制)

用什么数据结构实现状态树的功能？

1.哈希表

问题1：Merkel prove怎样提供 例如 如何证明账户余额？

        答：把哈希表的元素组成一个Merkel tree，算出一个根哈希值，并将根哈希值保存在区块头里。但如果有新区块发布，就会使得哈希表内容发生变化，下一次发布区块的时需要重新构建Merkel tree代价太大。 

2.Merkel tree

把所有以太坊账户构建成一个Merkel tree，但是Merkel tree无法提供一个有效的查找、更新的方法，Merkel tree中存在的问题

        不排序：查找困难，并且如果不固定账户在叶节点的顺序，生成的Merkel tree不是唯一的。

        排序：新增账户产生的地址是随机的，进行更新的时候代价非常大

3.MPT

addr->state

trie字典树：

特点：每个节点的分支数目取决于key值中每个元素的取值范围、不会发生碰撞、不同节点构建一样的tree、更新局部性好

缺点：存储浪费

Patricia tree压缩前缀树：

树的高度明显减小、访问内存的次数大大减少，但是新插入数据可能会导致树的路径扩展开。当key分布稀疏，压缩效果更好。

MerkelPatricia tree：

把普通指令换成哈希指令，也就是所有账户组成一个Patricia tree，用路径压缩提高效率，能够计算出一个根哈希值，写入区块头。

作用：防止篡改、Merkel proof（将账户所在分支向上的信息 发给轻节点，能够进行资产验证）、能够证明MPT中某个key不存在

Modified MPT：

 当新区块发布，部分节点的值会发生变化，这些节点的值，不会在原地改变 而是新建一些分支，原来的状态其实是保留下来的。

系统中的全节点需要维护的不是一棵MPT，而是每次出现一个区块都要新建一个MPT，只不过这些状态树中大部分节点都是共享的，只有少数发生变化的节点才新建分支。

问：为什么要保留历史状态？而不是在原地更改

答：以太坊虚拟机图灵完备，如果不保存历史记录，智能合约之后 很难推算出之前的状态。所以如果要支持回滚，就必须保存历史状态

问：状态树中保存的（key，value），key就是地址，value是账户的状态，那么是如何存储在状态树中的呢？

答：经过RLP（recursive length prefix）序列化

与protocol buffer 相比RLP只支持字符（字节）数组[nested array of bytes]，以太坊所有数据最终都会成为nested array of bytes，所以要实现一个RLP会更容易（难的）