区块链学习笔记（四）【Merkle树】

一、字典树

字典树的三个基本特征：

1、根节点不包含字符，为空，除根节点外每一个节点只包含一个字符

2、从根节点到某一个节点，路径上经过的字符连接起来，就是该节点对应的字符串

3、每个节点包含的所有子节点的字符都不相同

优势：

相比较于哈希表，使用字典树在查询共有前缀key的数据时十分高效，当前缀为空时，字典树和哈希表都需要遍历整棵树，此时效率相同。并且，字典树不存在哈希表的哈希冲突问题。

缺点：

直接查找的效率低，字典树查找效率为O（m），m为查找节点的key长度，哈希表查找效率为O（1）。

当没有相同前缀的分支时，存储key内容很长的字符串会十分浪费空间。

下面是一个and、as、at、cn、com构造的字典树的例子

二、Patricia树

是一种更加节省空间的字典树，对于每一个节点，如果该节点只有一个子节点，将当前节点和子节点融合，例子如下

三、Merkle树

比特币使用的交易存储结构。也称为hash树，其叶子结点是数据块（文件/文件集合）的hash值，非叶子结点是其对应子节点串联字符串的hash值。

在了解Merkle树之前，我们先了解下Hash List。在点对点网络传输中，我们会从多个机器上下载数据，那么就会存在机器不稳定或者不可信的问题，为了校验数据文件的完整性，我们会将大的文件分割成小的数据块，这样做的好处不仅加快速度，而且如果小的数据块在传输过程中损坏，只需重新下载这一数据块即可。为了确定小的数据块有没有损坏，我们为每个数据块生成一个hash，然后将所有的hash值拼到一起，再对这个长字符串进行hash运算，这样就得到了一个root hash。在下载数据的时候，首先从可信的数据源得到正确的root hash，就可以用他来校验hash list了，然后通过具体的hash来校验数据块。

Merkle树可以看成是Hash List的泛化。不同点在于，Merkle树将相邻的两个hash合并成一个字符串，然后运算生成一个新的hash，从下至上，直到生成一个root hash，如果hash的总数的单数无法配对，那么最后一个单数hash值可以直接进行hash运算或者复制自身组成字符串在进行hash运算。

Merkle树和Hash List的主要区别在于，Merkle树可以直接下载并验证树的一个分支，而hash list必须下载整个列表才能验证。

优点：

当树的节点内容发生变化时，可以快速的对被修改节点进行hash重计算，从而生成一个新的根哈希来代表整棵树的状态

在比特币中，轻节点只需要存储区块头数据，即根哈希的值，而不需要存储整个交易列表，使得区块链可以运行在PC和手机等终端上。

缺点：

存储整个数据的空间开销很大。