Bucket tree

结构解析

结构解析

bucket tree其实是揉合了两种不同的数据结构组合而成，这两种数据结构为：

merkle树
哈希表

因此在介绍bucket tree的结构之前，我们首先简要地介绍一下上述两种数据结构。

merkle树

Merkle树是由计算机科学家 Ralph Merkle 在很多年前提出的，并以他本人的名字来命名，在比特币网络中用到了这种数据结构来进行数据正确性的验证。

在比特币网络中，merkle树被用来归纳一个区块中的所有交易，同时生成整个交易集合的数字指纹。此外，由于merkle树的存在，使得在比特币这种公链的场景下，扩展一种“轻节点”实现简单支付验证变成可能。

特点

默克尔树是一种树，大多数是二叉树，也可以多叉树，无论是几叉树，它都具有树结构的所有特点；
默克尔树叶子节点的value是数据项的内容，或者是数据项的哈希值；
非叶子节点的value根据其孩子节点的信息，进行Hash计算得到的；

原理

在比特币网络中，merkle树是自底向上构建的。在下图的例子中，首先将ENTRY1-ENTRY4四个单元数据哈希化，然后将哈希值存储至相应的叶子节点。这些节点是Hash0-0, Hash0-1, Hash1-0, Hash1-1

将相邻两个节点的哈希值合并成一个字符串，然后计算这个字符串的哈希，得到的就是这两个节点的父节点的哈希值。

如果该层的树节点个数是单数，那么对于最后剩下的树节点，这种情况就直接对它进行哈希运算，其父节点的哈希就是其哈希值的哈希值（对于单数个叶子节点，有着不同的处理方法，也可以采用复制最后一个叶子节点凑齐偶数个叶子节点的方式）。循环重复上述计算过程，最后计算得到最后一个节点的哈希值，将该节点的哈希值作为整棵树的哈希。

若两棵树的根哈希一致，则这两棵树的结构、节点的内容必然相同。

采用merkle树的优势是：当某一个节点的内容发生变化时，仅需要重新计算从该节点到根节点路径上所有树节点的哈希，即可重新得到一个可以代表整棵树状态的哈希值。也正是因为merkle树的这个特点，使得bucket tree能够避免许多不必要的计算开销，拥有快速计算账户状态哈希的能力。

哈希表

哈希表，也称散列表，是大家非常熟悉的数据结构，是根据键（key）而直接访问在内存存储位置的。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

有关于哈希表的描述，在此就不再赘述了。在bucket tree中，使用哈希表来维护原始的数据。

bucket tree由两部分组成：底层的哈希表以及上层的默克尔树。也就是bucket tree其实是一棵建立在哈希表上的默克尔树。

哈希表由一系列哈希桶（bucket）组成，每个桶中存储着若干被散列到该桶中的数据项（entry），所有数据项按序排列。每一个桶有一个哈希值用来表示整个哈希桶的状态，该哈希值是根据桶内所有数据项的内容进行哈希计算得到。

除了底层的哈希表以外，上层是一系列的merkle树节点。一个merkle树节点对应着下一层的n个哈希桶或者merkle树节点。这个n也称作merkle树的聚合度。该merkle树节点中维护着这n个孩子节点的哈希值，且merkle树节点本身的哈希值是根据这n个孩子节点的哈希值计算得到。

如此不断迭代，最终最上层的树节点是整棵树的根节点，该节点的哈希值就代表着整棵树的哈希。

如此设计的目的是：

利用merkle树的特点，使得每次树状态改变，重新哈希计算的计算代价最小；
利用哈希表进行底层数据的维护，使得数据项均匀分布；

例如上图中，一条新的数据项entry5插入，该数据项被散列到POS为2的桶中。该桶，即从该桶至根节点上所有的节点被标为粉红色，即为脏节点。仅对这些脏节点进行哈希重计算，便可得到一个新的哈希值用来代表新的树状态。

由于bucket tree是一棵固定大小的树（即底层的哈希表容量在树初始化之后，就无法更改了），随着数据量的增大，采用散列函数将所有的数据项进行均匀散列可以避免数据聚集的情况发生。

此外，bucket tree有两个重要的可调参数：

capacity
aggreation

前者表示哈希表的容量，该值越大，整棵树相对来说能够容纳的数据项的个数就越多，在聚合度不变的前提下，树高越高，从叶子节点到根节点路径上的树节点个数也越多，哈希计算次数增加；

后者表示一个父节点对应的孩子节点的个数，该值越大，表示树的收敛速度越快，在哈希表容量不变的前提下，树高更低，从叶子节点到根节点路径上的树节点个数也越少，哈希计算次数减少；但是每个默克尔树节点的size就越大，增加数据库IO开销；

哈希桶

哈希桶的定义如下，由一系列的数据项组成，注意这些数据项是按key的字典序排序的，每一个数据项即代表了一条用户数据（可以优化为仅存储用户数据的哈希值）。

type Bucket []*DataEntry

merkle节点

merkle节点的定义如下，主要的字段为与其相关的孩子节点列表，该列表中的每一个元素都是一个孩子节点的哈希值。

// MerkleNode merkleNode represents a tree node except the lowest level's hash bucket.
// Each node contains a list of children's hash. It's hash is derived from children's content.
// If the aggreation is larger(children number is increased), the size of a merkle node will increase too.
type MerkleNode struct {
    pos      *Position
    children [][]byte
    dirty    []bool
    deleted  bool
    lock     sync.RWMutex
    log      *logging.Logger
}