在之前的EVM系列的文章中,其实一直有一个问题没有解决,那就是Storage持久化的数据最终是以什么样的形式,保存在哪里?数以万计的合约有数以万计的storage变量,这些变量如何快速的读写?

字典树(Trie)

Trie又称前缀树或字典树,是一种有序多叉树。下图是一颗典型的前缀树;

图中前缀树存储了一些字符串,蓝色的是关键字,存储的字符串由关键字组成。存储了”a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”。
前缀树有这些特点;

  • 根节点不包含字符,其他节点各包含一个字符;
  • 关键路径节点的字符连接起来为该节点所存储的数据;

关键路径就是每个节点有一个标志位,用来标记这个节点是否作为构成数据的一部分,上图中的,t, e 节点就不是关键路径。

Trie的核心思想就是用空间换时间,利用公共前缀缩小要比较的范围来达到快速查找的目的。

优点
  • 插入和查询的效率都很高,都是O(m),m是插入或查询字符串的长度。
  • 可以对数据按照字典序排序。
缺点
  • 空间消耗的比较大。
典型场景
  • 但词频次统计。
  • 字符串匹配。
  • 字符串字典序排序。
  • 前缀匹配,比如一些搜索框的自动提示。

压缩字典树

压缩字典树在字典树的基础之上做了一些优化,具体可以看下图;

图中黑色的是关键路径,存储了字符串”abc”和”d”,但是明显可以看到压缩后的前缀树占用了更小的空间。

默克尔树(Merkle tree)

默克尔树首先计算叶子节点的hash值,然后将相邻两个节点的哈希进行合并,合并完成后计算这个字符串的哈希值,直到根节点为止,如果是单个节点,可以复制单节点的哈希,然后合并哈希再重复上面的过程。

优点

可以高效安全的验证数据结构的内容。

典型场景

p2p网络分块下载文件的时候,快速校验下载到的数据是否完整,是否遭到破坏。

默克尔帕特里夏树(Merkle Patricia Tree)

MPT树结合了字典树和默克尔树的优点,在压缩字典树中根节点是空的,而MPT树可以在根节点保存整棵树的哈希校验和,而校验和的生成则是采用了和默克尔树生成一致的方式。
以太坊采用MPT树来保存,交易,交易的收据以及世界状态,为了压缩整体的树高,降低操作的复杂度,以太坊又对MPT树进行了一些优化。将树节点分成了四种;

  • 空节点(hashNode)
  • 叶子节点(valueNode)
  • 分支节点(fullNode)
  • 扩展节点(shortNode)

通过以太坊黄皮书中很经典的一张图,来了解不同节点的具体结构和作用

可以看到有四个状态要存储在世界状态的MPT树中,需要存入的值是键值对的形式。自顶向下,我们首先看到的keccak256生成的根哈希,参考默克尔树的Top Hash,其次看到的是绿色的扩展节点Extension Node,其中共同前缀shared nibble是a7,采用了压缩前缀树的方式进行了合并,接着看到蓝色的分支节点Branch Node,其中有表示十六进制的字符和一个value,最后的value是fullnode的数据部分,最后看到紫色的叶子节点leadfNode用来存储具体的数据,它也是对路径进行了压缩。

在智能合约执行以后,有一部分数据是需要持久化,参考「EVM深度分析之数据存储(一)」中的Storage中的类型,而一条链上有非常多的合约,每个合约又有很多的数据需要持久化,这个时候就需要用到MPT树。

在「EVM深度分析之数据存储」中可以看到需要持久化的数据都是以键值对的形式存在的,而键是由keccak256这个函数计算得到,用十六进制表示后刚好对应 MPT 树中分支节点的0-f的16个分支。

为了避免不同合约有相同的字段,合约又通过地址来进行管理,具体参考「以太坊账户组织形式」,本质上也是采用MPT树管理合约,合约又采用MPT树管理自身状态。

最终的数据还是以键值对的形式存储在LevelDB中的,MPT树相当于提供了一个缓存,帮助我们快速找到需要的数据,至于最终落盘的数据后面在讲~