状态树

        状态树用来实现账户地址到账户状态的映射。以太坊中采用Modified Merkle Patricia Tree来实现状态树的功能。

        值得注意的是,一个账户在刚被创建时,其他用户是不知道该账户是否存在的。只有在该账户与其他账户发生交易时,会在状态树中新插入一个结点,这时其他账户才会知道该新建账户的存在。

压缩前缀树

        首先,什么是前缀树?

        前缀树又称为字典树,是一种有序树,用于保存关联数组,其中的键通常是字符串。与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。一般情况下,不是所有的节点都有对应的值,只有叶子节点和部分内部节点所对应的键才有相关的值。(参考百度百科

前缀树

        但是前缀树的一个缺点,对存储空间有一定的浪费。其解决办法是,对于前缀树的每个节点,如果该节点是确定的子树的话,就和父节点合并。这样就得到了压缩前缀树(Patricia Tree)。
压缩前缀树

        键值分布比较稀疏的时候,路径压缩效果比较好。

        而将压缩前缀树的指针变为哈希指针,就得到了Merkle Partricia Tree(MPT)。

        以太坊中对MPT进行了一定的优化,采用Modified MPT来实现账户地址到账户状态的映射,查找的键值是账户地址。如下图所示。

Modified MPT

        Modified MPT中,如果有一个用户的状态发生了变化,会向树中增加分支,而不是直接在树中进行修改,从而实现保存历史记录。
        那么,为什么以太坊中需要保存用户状态的历史记录,而比特币中不需要呢?
        因为,比特币中区块生成速度较慢,产生分叉的可能性也较低。而且,即使产生了分叉,由于比特币系统中的交易比较简单,只是简单的转账交易,因此回滚起来比较方便。比较容易实现将被抛弃的分叉中的交易进行回滚。
        而以太坊就不一样了。以太坊的区块生成速度比较快,十几秒就会产生一个区块,因此产生分叉非常频繁,需要经常进行回滚操作。最重要的一点是,以太坊中有智能合约,使得以太坊是图灵完备的,可以实现很复杂的交易。因此,如果不保存历史记录,就很难进行回滚操作。

交易树

        每当发布一个区块时,区块中包含的所有交易,会被组织成一棵交易树,该树是一棵Merkle Patricia Tree,查找的键值是交易在发布时的序号(交易的排列顺序是由发布区块的节点决定的)。
       交易树用来证明某笔交易在某个区块当中。
        以太坊可以看做是一个交易驱动的状态机。交易是指发布的区块中所包含的交易,状态是指状态树中的账户状态。这些交易会驱动整个以太坊从当前的状态转移到下一个状态。

布隆过滤器(Bloom filter)

        在介绍收据树之前,首先需要认识一下Bloom filter。
        Bloom filter 是由 Howard Bloom 在 1970 年提出的二进制向量数据结构,它具有很好的空间和时间效率,被用来检测一个元素是不是集合中的一个成员。该数据结构目前常被用于海量数据处理。
        如需要判断一个元素是不是在一个集合中,我们通常做法是把所有元素保存下来,然后通过比较知道它是不是在集合内,链表、树都是基于这种思路,当集合内元素个数的变大,我们需要的空间和时间都线性变大,检索速度也越来越慢。而Bloom filter则可以对该问题有比较好的解决。(参考百度百科
        Bloom filter 采用的是哈希函数的方法,将一个元素映射到一个 m 长度的阵列上的一个点,当这个点是 1 时,那么这个元素在集合内,而当这个点是0时,则不在集合内。但Bloom filter有一个局限性,不支持删除操作,因为有可能有多个元素映射到同一个点上,如果对一个元素执行了删除操作,其他的元素也会受到影响。
        注:通过bloom filter,在某个区块中的交易一定可以被证实,但不在该区块中的交易也有可能被误证实在里面(可能出现误报,但不会出现漏报)。

收据树

        每个交易执行完之后,会形成一个收据,记录交易的相关信息,而这些收据会被组织成一棵收据树,该树是一棵Merkle Patricia Tree,查找的键值是交易在发布时的序号(交易的排列顺序是由发布区块的节点决定的)。
        那么,既然已经有了交易树,为什么还需要收据树这个数据结构呢?
        因为,以太坊拥有智能合约,而智能合约的执行过程比较复杂,通过增加收据树,有利于系统快速查询执行的结果。
        在以太坊中,每个交易对应的收据中都会包含一个Bloom filter,记录这个交易的类型、地址等信息。发布的区块的块头中也有一个总的Bloom filter,这个Bloom filter是所有收据中的Bloom filter的并集。
        如果我们需要查找过去一段时间内发生的和某个智能合约相关的所有交易,首先需要在区块的块头中的Bloom filter中看看有没有我们要查找的交易的类型,如果有的话,再到区块中的每个交易对应的收据的Bloom filter中进行查找;而如果没有的话,那么该区块中一定没有我们要查找的交易类型。通过该种方法,就可以快速排除掉无关的收据,从而提高查找速度。

本文参考:https://www.youtube.com/watch?v=RADwCuRRoFs&list=PLnTPdMjBRmAYehJkVbAXqxO-0cc9ALC6V&index=17