在学习课程的时候，你也可以免费领取BaaS平台为期一个月的试用机会，免费使用高性能区块链服务（点击文末的原文链接即可免费领取）。课程学习结合实践操作，让你迅速成为区块链大牛！ *以下为第七课的内容~ 第七课 主流区块链数据存储分析 — 以太坊 数据结构 MPT全称Merkle Patricia Trie，是以太坊用来组织管理账户数据、生成交易集合哈希的重要数据结构, 它融合了Trie、Patricia Trie、Merkle Tree这3种数据结构的优点，如下图所示： ' MPT数据结构演变过程 在介绍MPT之前，我们首先简要地介绍一下其它几种树的特点： Trie Trie树，又称前缀树或字典树，是一种用于快速检索的多叉树结构，其中的键通常是字符串，如英文字母的字典树是一个26叉树，数字的字典树是一个10叉树。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，根节点对应空字符串。实际上trie每个节点是一个确定长度的数组，数组中每个节点的值是一个指向子节点的指针，最后有个标志域，标识这个位置为止是否是一个完整的字符串。
Trie树的优点是最大限度地减少无谓的字符串比较，查询拥有共同前缀key的数据时十分高效；缺点是内存消耗大，尤其是前缀不重复的情况下，其次直接查询效率没有哈希表高。 Patricia Trie Patricia Trie称为压缩前缀树，是一种更节省空间的Trie。对于每个节点，如果该节点是唯一的儿子的话，就和父节点合并。
Merkle Tree Merkle Tree在前面一篇文章有介绍，这里不再过多介绍。 Merkle Patricia Trie Merkle Patricia Trie是一种经过改良、融合了默克尔树和前缀树两种树结构优点的数据结构。在以太坊中，为MPT树新增了几种不同类型的树节点(空节点、分支节点、叶子节点、扩展节点)，以尽量压缩整体的树高、降低操作的复杂度： 1) 在key之前增加一个4bit的flag前缀，其中最低位用来编码原本key长度的奇偶信息，key长度为奇数，则该位为1；低2位中编码一个特殊的终止标记符，若该节点为叶子节点，则该位为1； 2) 若原本key的长度为偶数，则在key之前再增加一个值为0x0的4bit前缀，因为在十六进制编码中一个字节用两个字符表示，所以总的字符长度必须是偶数，这一步属于补位操作；
扩展节点和叶子节点几种Prefix 经过改良和融合之后的Merkle Patricia Trie也形成了自身的特性：
四个kv数据十六进制编码转换 如上图所示先把要存储的数据key值进行十六进制编码，由于key已经是十六进制的数据，所以不需要再编码，只是把key值按每个十六进制数一个字节组织起来，便于使用MPT数据结构来管理这些数据。
上图所示就是刚才处理之后的四个kv数据使用MPT结构组织的示意图，从这个图中可以看到分支节点、扩展节点和叶子节点的结构。分支节点之所以十六个数组再加一个value字段，是因为在以太坊中所有的key值都是十六进制的，所以key值里面的数字全部在0-f范围内；叶子节点和扩展节点结构完全一样，根据prefix来进行区分，prefix的值是按照Hex-Prefix编码得得到的，叶子节点的value是真实要存储的数据，扩展节点的key存储的是子节点共有的key，value指向下一个节点。当数据在内存中时按照上图组织，但当这些数据要存储到磁盘时，节点之间的关联关系就需要变成hash引用。从内存结构演变成存储到磁盘的kv过程如下两图所示：
从上面两张图可以看到节点之间由hash建立关联关系，并把每个节点编码成kv数据存储格式的过程。根节点的hash就是整棵树的HashRoot，每个节点按照kv方式存储到磁盘，在需要的时候可以根据HashRoot把整棵树在内存中还原，也可以单独根据节点的hash访问单个节点。 区块和交易 以太坊区块结构和比特币相似，由Header和Data组成，且它们都是采用的POW共识算法，所以POW相关的字段都有，区别在于以太坊的Header中多了两个关键的State Root和Receipt Root字段，下图所示为以太坊区块示意图：
上述三种HashRoot分别对应着三个MPT结构，而这些MPT结构都与区块息息相关。MPT组织数据的过程，在前面我们已经举例说明了，这里不再详述，区别就是数据源不一样，key值不相同。图中还有一个storage Trie，这也对应着一个MPT结构，这个树属于每个账户，后面详细介绍。在区块中的数据Data字段，包含了区块打包的所有交易，交易的数量会受到Header中GasLimit的限制。
上图所示就是Transaction Root的计算过程，把一个区块中所有的交易用MPT组织，根节点的hash就是需要的数据。这里可以看到写入MPT的kv数据，key值是单个Transaction在整个交易列表中序号的(0,1,2,…)rlp编码值，value是Transaction的rlp编码值。rlp编码是以太坊结构体序列化的主要编码方式，它的内部实现细节这里不详细介绍，可以查阅相关文档。
区块序列化成kv数据 在以太坊中所有数据都存储在leveldb数据库，即所有要存储的数据都以kv方式存储，这和比特币用文件存储区块数据不太一样。上图所示为一个区块序列化成kv数据的过程，单个区块序列化成两个kv，一个存储header信息，key为标识符小写字母h+区块号+区块Hash， value为Header数据的rlp编码；一个存储Data信息，key为标识符小写字母b+区块号+区块Hash， value为Data数据的rlp编码。 除了区块序列化之外，以太坊为了高效的查询建立了很多索引，这些索引信息也以kv方式存储在leveldb数据库，例如上图中的交易信息索引。交易信息索引信息key为小写字母l+交易hash，value为结构体（TxLookupEntry）的rlp编码值。再列举几个： 当然以太坊中的索引信息不止上面列举的这些内容，正是由于这些索引信息的存在，在业务层使用过程中才会高效的查询到需要的数据信息，包括区块浏览器从各个维度查询。 账户状态 区块链中的账户和银行系统的账户类似，就是记录资产的一个地址。在以太坊中有两种账户——普通账户和合约账户：用于个人数字资产记录的账户称为普通账户，这类账户由私人密钥控制，拥有者可以查询余额，可以创建和签名一笔交易发起转账或者支付；区块链为成功部署于其上的合约代码和数据生成的帐号称为合约账户，它是代码(它的功能)和数据(它的状态)的集合。这两类账户的数据使用相同结构来记录，即Account：
在Account中有Nonce、Balance、Storage Root、Code Hash四个属性值。Nonce是一个递增的整数值，用来标记每个账户发起交易时的交易序号，成功发起一笔交易该值就加1；Balance记录账户的资产余额；Storage Root和Code Hash是针对合约账户的，Storage Root是合约代码在evm中执行完成后，所有成员变量以MPT组织之后的根节点的hash，而Code Hash就是合约账户对应的合约代码的hash。 在以太坊中，每个账户(Address)对应着一个StateObject，StateObject包含一个Account，每个block对应一个完整的包含所有address的状态信息即StateObject的集合，可以称为账户状态。和block对应的账户状态使用MPT格式存储，即前面提到的State Trie，block中记录State Trie根节点的hash。使用MPT来存储账户的好处是每个block对应的State Trie可以只存储和计算有变化的节点，未变化的节点可以直接使用hash引用前面一个区块存储的节点，节省资源空间，提高存储效率。
两个State Trie的变化实例 假设 |
