四种树的区别

Merkle树

Merkle Tree，也叫做哈希树，顾名思义，就是存储hash值的一棵树。Merkle树的叶子是数据块的hash值。非叶节点是其对应子节点串联字符串的hash。是一个把任意长度的数据通过哈希函数映射成固定长度数据，这个数据就叫hash值，将这些hash值放到一个List里面，就叫做Hash List。Merkle Tree可以看做Hash List的泛化。

Trie 树

Trie树，又称前缀树或字典树。利用字符串的公共前缀来减少查询时间，最大限度的减少无谓的字符串比较，查询效率比哈希树高。典型应用是用于统计，排序和保存大量的字符串(不仅限于字符串)，经常被搜索引擎系统用于文本词频统计。

Patricia树

Patricia树，或称Patricia trie，压缩前缀树，是一种更节省空间的Trie。对于基数树的每个节点，如果该节点是唯一的儿子的话，就和父节点合并。