以太坊中最常用的三种树结构介绍

树数据结构在区块链中扮演着重要的角色。 交易数据、账户管理、交易收据信息都基于一棵树。 本文主要介绍三种树，也是以太坊中使用最多的三种树结构：Trie树、Patricia Trie和Merkle树。

特里树

Trie 树，也称为词典树、单词搜索树或前缀树，是一种用于快速检索的多叉树结构。 例如，英文字母的字典树是26-tree，数字的字典树是10-tree。 比如用trie树保存10个节点的6个字符串：tea,ten,to,in,inn,int。 具体图片如下：

可以看出，in、inn、int这三个字符串的共同前缀是“in”，起到了压缩数据，减少存储空间的作用。 那么如果没有共同的前缀，那么问题就来了，会占用大量的空间，检索速度也会变慢。

·帕特里夏·特里

Patricia Trie 树的不同之处在于Trie 树为每个字符串分配一个节点以太坊数据结构，这会将很长但没有公共节点的字符串的Trie 树退化为一个数组。 在以太坊中，许多这样的节点将被黑客构建以引起拒绝服务攻击。 与前缀树的区别在于，如果节点共享一个前缀，则使用公共前缀，否则将所有剩余节点插入同一节点。 Patricia相对于Tire的优化如下图所示：

我们可以举个例子来总结一下Patricia Trie树，如下图：

最后8个键对应的值如下：

·默克尔树

所谓哈希树，顾名思义，就是一种存储哈希值的树。 Merkle 树的叶子是数据块（例如，文件或文件集合）的哈希值。 非叶节点是其相应子节点的串联字符串的散列。 这种树结构就是比特币采用的数据结构。 Merkle Tree的主要作用就是当我得到Top Hash的时候，这个hash值代表了整棵树的信息汇总。 当树中的任何数据发生变化时，Top Hash 的值都会发生变化。 Top Hash 的值将存储在区块链的区块头中，区块头必须通过工作量证明。 也就是说，只要拿到区块头，就可以验证区块信息。

· ETH Merkle Patricia Tries

以太坊中的每个区块头都包含三个重要的树：

1.交易树

2.收据树（交易执行过程中的一些数据）

3.状态树（账户信息、合约账户和用户账户）

下面举例介绍，比如两个区块头，其中state root，tx root receipt root分别存放了三棵树的根，第二个区块显示的是账户175的数据变化（27 -> 45） ，只需要存储与该账户相关的部分数据，旧区块中的数据仍然可以正常访问。 如下所示：

· 算法解释

假设输入值J包含一组Key Value对（Key Values都是字节数组）：

在使用这个集合时，我们将集合表示如下：

对应一个特定的字节，我们将其表示为对应的半字节，其中Y集合在Hex-Prefix Encoding中描述，表示半字节（4bit）集合（使用半字节的原因与后面的描述不同）分支节点的分支节点结构与key中的编码标志相关），公式如下：

Tries树中的节点分为三种：

1.叶子节点（Leaf）：叶子节点包含两个字段，第一个字段是剩余Key的半字节编码，半字节编码方式的第二个参数为true，第二个字段为Value

2. 扩展节点（ExtenTIon）：扩展节点也包含两个字段，第一个字段是剩余的至少两个节点可以共享的Key的半字节码，第二个字段是n(J,j)

3.分支节点（Branch）：一个分支节点包含17个字段，其中的前16项分别对应其遍历中这些点的key的16个可能的半字节值。 第17个字段是存放那些以当前节点结束的节点（比如有3个key，分别是(abc, abd, ab)，第17个字段存放的是ab节点的值）

分支节点仅在需要时使用。 对于只有一对非空键值对的 Trie 树，可能没有分支节点。 如果用公式来定义这三个节点，公式如下：图中的HP函数表示Hex-Prefix Encoding，是一种半字节编码格式，RLP是使用RLP进行序列化的函数。

如果当前KV集合中只剩下一条数据需要编码，那么这条数据就按照第一条规则进行编码。

如果当前需要编码的KV集合有公共前缀，则提取最大的公共前缀以太坊数据结构，使用第二条规则进行处理。

如果不是以上两种情况，则使用分支节点进行集合切分，因为key是使用HP编码的，所以可能的分支只有0-15的16个分支。 可以看出u的值是由n递归定义的，如果一个结点刚好在这里结束，那么第17个元素v就是为这种情况准备的。

黄皮书中没有明确定义数据应该和不应该如何存储。 所以这是一个实施问题。 我们简单地定义一个函数来将 J 映射到一个 Hash。 我们认为对于任意一个J，只有一个Hash值。