merkle树、Trie树、MPT树、以太坊中的那些树

以太坊中的树，先再啰嗦下merkle树。在比特币中使用了merkle树的数据结构，那么在以太坊中针对三种对象设计了三课merkle树。称为（merkle patricia树）。分别对应：状态树、交易树、收据树。那么这些树能简单帮助以太坊客户端做一些简单的查询验证。

顺带提一句，所有区块和交易的数据都是存在在levelDB数据库中，在levelDB数据库中一个key-value的模式，其中value存储的内容根据RLP编码。

Merkle树之前有过介绍，这里就不展开了，首先说下Trie树。

Trie树

Trie树也叫做Radix树，又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。

优点：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

树中的key（这个不是币乎的key币~~~），代表是从树根root，到对应的value的一条路径，且这条路径真实可靠。那么从root根节点开始，key中每一个字符都代表一条路径，一条从root开始到你需要寻找的对应的value说经历的所有子节点。value的值存储在子节点。那么假设key中的字符在一个容量为n的不重复字母表，那么每个节点最多有n个孩子节点，树的深度就还是key的最大的长度。

Trie树优点有很多，上面简述了一个，这里再详细分解下：我们假设在一个Trie树中有两个value，且有两个相同的前缀key，那么相同前缀的长度占自身比例越大，那么两个value位置越接近。且不会类似散列表中的冲突，保证了一个key对应一个value。

Trie树缺点，那么就是一个存储不平衡的问题，设想下一个长度比较长的key，树中没有其他key有相同的前缀，那么去查询这个存储key和value就需要遍历相当多的节点，这样导致这个树不平衡。

Merkle Patricia树

Merkle Patricia Tree(简称MPT树，实际上是一种trie前缀树)是以太坊中的一种加密认证的数据结构，可以用来存储所有的(key，value)对。以太坊区块的头部包括一个区块头，一个交易的列表和一个uncle区块的列表。在区块头部包括了交易的hash树根，用来校验交易的列表。在p2p网络上传输的交易是一个简单的列表，它们被组装成一个叫做trie树的特殊数据结构，来计算根hash。值得注意的是，除了校验区块外，这个数据结构并不是必须的，一旦区块被验证正确，那么它在技术上是可以忽略的。但是，这意味着交易列表在本地以trie树的形式存储，发送给客户端的时候序列化成列表。客户端接收到交易列表后重新构建交易列表trie树来验证根hash。RLP(Recursive length prefix encoding,递归长度前缀编码)，用来对trie树种所有的条目进行编码.参考：http://www.cnblogs.com/fengzhiwu/p/5565559.html

针对merkle树和Trie树的特点，以太坊对其改进。

目标一：保证树的加密安全，那么每个节点的散列值引用，在levelDB中查询。在非叶节点，数据的表现形式：key代码RLP编码的SHA3散列值，value是节点RLP编码。在获取一个节点的内容，只要根据节点的散列值去访问数据库然后获得RLP编码，解码即可。

目标二：引入多节点来提高效率。Merkle Patricia Tree节点分为下面几种，

1.空节点，就理解为一个空串。

2.叶节点，键值对应为列表，key为16进制编码，value是RLP编码。

3.扩展节点，键值对应列表，value是其他节点散列值，通过这个散列值去链接到其他的节点。

4.分支节点，长度为17的列表，key还是编码为16进制编码，加上value，前16个元素对应key的16个十六进制字符，如果一个键值在这个分支终止了，那么最后的一个元素表示为一个值。分支节点既是搜索的终止也可是路径的中间点。

MPT树中是16进制的hex-prefix，HP编码，对key编码。所以每个节点可能有16个孩子，引入一种特殊的终止标识符来标识key所对应的值是真实的值，还是其他节点的hash值。

一旦终止标识打开，那么key是叶节点，对应真实的value。

终止标识关闭，那么值就是在数据块中查询对应节点的hash。

不论key是奇偶长度，HP对其编码后，一个单独的hex字符或者4bit二进制数字，称为一个nibble。如下图：

一个nibble加上key前面，对终止奇偶符编码，最低位标奇偶性，第二低位编码终止符状态，一旦key是偶数，那么加上另外一个nibble，值0来保证整体的偶性。

MPT树操作

MPT树更新：

更新函数：_update_and_delete_storage(self,node, key, value)针对四种节点。

Node空节点：直接返回[pack_nibbles(with_terminator(key)), value]，即对key加上终止符，然后进行HP编码。

Node分支节点：那么key为空时，说明更新的是分支节点的value，直接node[-1]设置为value。那么key不为空时，递归更新key[0]位置为根的子树，顺着key向下找，使用_update_and_delete_storage(self._decode_to_node(node[key[0]]),key[1:], value)

Node是叶子节点或者扩展节点：调用_update_kv_node(self, node, key, value)

curr_key是node的key，找到curr_key和key的最长公共前缀，长度为prefix_length。Key剩余的部分为remain_key，curr_key剩余的部分为remain_curr_key

再分以下情况：

remain_key==[]==remain_curr_key，key和curr_key相等，那么如果node是叶子节点，直接返回[node[0], value]。如果node是扩展节点，那么递归更新node所链接的子节点，即调用：

_update_and_delete_storage(self._decode_to_node(node1),remain_key, value)

remain_curr_key== []，即curr_key是key的一部分。如果node是扩展节点，递归更新node所链接的子节点，即调用:

_update_and_delete_storage(self._decode_to_node(node1),remain_key, value)；如果node是叶子节点，那么创建一个分支节点，分支节点的value是当前node的value，分支节点的remain_key[0]位置指向一个叶子节点，这个叶子节点是[pack_nibbles(with_terminator(remain_key[1:])), value]

创建一个分支节点。如果curr_key只剩下了一个字符，并且node是扩展节点，那么这个分支节点的remain_curr_key[0]的分支是node1，即存储node的value。否则，这个分支节点的remain_curr_key[0]的分支指向一个新的节点，这个新的节点的key是remain_curr_key[1:]的HP编码，value是node1。如果remain_key为空，那么新的分支节点的value是要参数中的value，否则，新的分支节点的remain_key[0]的分支指向一个新的节点，这个新的节点是[pack_nibbles(with_terminator(remain_key[1:])),value]

key和curr_key有公共部分，为公共部分创建一个扩展节点，此扩展节点的value链接到上面步骤创建的新节点，返回这个扩展节点；否则直接返回上面步骤创建的新节点。

删除老的node，返回新的node。

https://www.cnblogs.com/fengzhiwu/p/5584809.html

链接中有些详细图解，有兴趣可参考，步骤分明。

MPT树删除操作：

删除函数：_delete_and_delete_storage(self,key)

同样和更新分多种情况：

Node为空节点，那么直接返回。

Node为分支节点，如果key为空，那么表示删除了分支节点的值，node[-1]=‘’，返回node的正规化的结果。如果key不为空，递归查找node的子及诶单，删除对应的value，调用elf._delete_and_delete_storage(self._decode_to_node(node[key[0]]),key[1:])。返回新节点。

Node为叶子节点或者扩展节点，curr_key是当前node的key。一种情况，如果key不是以curr_key开头，说明key不在node为根的子树内，直接返回node。另一种情况，如果node是叶节点，返回BLANK_NODE if key == curr_keyelse node。Node是扩展节点的话，递归删除node的子节点，即调用

_delete_and_delete_storage(self._decode_to_node(node1),key[len(curr_key):])。如果新的子节点和node[-1]相等直接返回node。否则，如果新的子节点是kv节点，将curr_key与新子节点的可以串联当做key，新子节点的value当做vlaue，返回。如果新子节点是branch节点，node的value指向这个新子节点，返回。

MPT树查找：

查找函数：_get(self, node, key)

Node为空节点，那么直接返回。

Node是分支节点，key为空，返回分支节点的value；否则递归查找node的子节点，即调用_get(self._decode_to_node(node[key[0]]),key[1:])

Node是叶子节点，返回node1 if key == curr_key else ‘’

Node是扩展节点，key以curr_key开头，递归查找node的子节点，即调用_get(self._decode_to_node(node1), key[len(curr_key):])；否则，说明key不在以node为根的子树里，返回空。

在以太坊的安全树中采用SHA3（k）作为密钥，状态树和账户存储树中均使用。通过设置离散节点的链深度为64，反复用sload和sstore指令，有效防范Dos攻击。