1.数据结构及算法

1.1 SHA-3

以太坊中用到的hash算法，或者叫Keccak256。

1.2 RLP编码

RLP(Recursive Length Prefix，递归的长度前缀)，以太坊中用到的编码格式，用来序列化和反序列化数据。如将对象进行RLP编码后保存在levelDB数据库中，再从数据库中取出后解码为对应的对象等。

1.3 MPT

一种压缩前缀树，结构如下图所示：

图中有几种节点：

Extension Node：包含了该节点的路径shared nibbles，以及下一个节点的指针next node

Branch Node：包含了一个长度为17的数组，前面16个分别表示从0到f这16进制下挂载的节点位置，最后一位表示当前节点数据。

Left Node：叶子节点，包含了key路径和value数据。

按图中数据打比方说，当有如下几个key-value需要组织成mpt树时：

存储这4组数据的4个叶子节点会有个共同的Root节点，Root节点中会有个共同的key前缀a7。

从Root往下会分出一个Branch Node，在该Branch Node的第2个位置上（代表key1）挂载着key-end为1355，value为45.0ETH的叶子节点。该叶子节点的完整key为：Root中的key（a7）+Branch Node中第二个位置代表的key（1）+该叶子节点的key-end（1355）=a711355。同理a7f9365这个叶子节点也是如此。

然后是a77d337和a77d397这两个节点。由于这两个节点有更长的共同前缀a77d3，所有从【2】中的Branch Node的第8个位置上（代表key7）再挂载一个key为d3的Extension Node，然后该Extension Node再接上一个Branch Node用于挂载叶子节点。

将a77d337和a77d397分别挂载在【3】中的第4位（代表key3）和第10位（代表key9），他们的key-end都为7 (1)Root中的key（a7）+Branch Node中第二个位置代表的key（7）+【3】中Extension Node的key（d3）+挂载的第4位（3）+自己的key-end（7）=a77d337 (2)Root中的key（a7）+Branch Node中第二个位置代表的key（7）+【3】中Extension Node的key（d3）+挂载的第10位（9）+自己的key-end（7）=a77d397

在以太坊的实际应用中，当用MPT树管理所有的账户信息时，真正的key为账户的地址，账户地址为20byte，value为该账户信息的rlp编码内容。

以上说的是MPT树的节点组织形式，另外各个节点上还有一个非常重要的属性就是节点的hash。节点的hash值计算方式可以用下图表：

叶子节点的hash值为叶子节点对应数据的hash，其父节点的hash为所有叶子节点的hash相加再取hash值。一直到最上层的root节点会有个。这样的话只要某个叶子节点中的数据有所变化，从根节点到该叶子节点的路径上所有节点的hash值都会改变。当矿工挖出一个block，其中打包了一些交易对账户产生影响时对应的MPT树变化如下：

上图表示每个Block的Header中有一个State Root（其他字段后面会具体说明，暂时忽略他们）表示该区块高度时状态树的root hash，状态树是一颗用来管理以太坊中所有账户的MPT树，而每个账户中又有一个Storage root，通过该Storage root能找到保存在账户下的存储信息。

上图的含义是：

当一个用户账户下存储内容有所改变，其对应的Storage root会有所改变，对应的该账户节点的hash也会发生变动。

一个叶子节点的hash变动后，会重新计算其父节点的hash值，最终会得到一个新的root hash。

产生的新的root hash会被挂载到新的block上。

虽然用户账户的地址是固定的，但是由于不同的block中的State Root不一样，所以根据相同的账户地址，会查找到不同时期的账户信息。BlockN通过他的State Root查找到的是高度为N时的账户信息，而BlockN+1通过他的State Root查找到的是高度为N+1时的账户信息。

MPT树的节点信息都会保存在以太坊底层的数据库中。

1.4 存储

MPT树是以太坊中组织数据用到的一种数据结构，而在以太坊底层使用的LevelDB作为数据库来存储用到的数据。存储方式是用key-value的键值对，部分key-value如下表：

该表中的key可以在中查看到。

在底层LevelDB中存储着很多账户信息，key为账户Account的地址address，value为Account的RLP编码。当需要把这些Account从LevelDB中读取出来后，会将这些Account信息组织成一个逻辑上的MPT树。

下一篇写以太坊的账户结构相关的内容。