以太坊源码分析---go-ethereum之MPT(Merkle-Patricia Trie)

本文微信公众号 月牙寂道长 文章链接为：

本文图片可能不太清晰，看清晰版本的，可以看原文链接微信公众号链接。

MPT（Merkle-Patricia Trie）其实就是一个数据结构，在以太坊中用于存储用户账户的状态及其变更、交易信息、交易的收据信息。

要讲MPT，就要讲讲MPT是如何演变来的。

Trie

图片来自https://en.wikipedia.org/wiki/Trie

trie树，又称为字典树或者前缀树 (prefix tree)。这个数据结构，以前也有写过库，当然是用在自己的项目中。通过对字符的直接索引，减少字符串比较的动作，从而达到查询效率高。

但其也存在一些问题。

当有一个很长的字符串的时候，这个字符串又和其他字符串没有重叠的话，那那么在trie中，存储和遍历都需要很多的节点，并且会导致trie树不平衡。

Patricia Trie （Radix tree）

图片来自https://en.wikipedia.org/wiki/Radix_tree

Patricia Trie，又被称为 Radix Tree 或紧凑前缀树 (compact prefix tree)。是在trie上优化过来的。主要的优化是，如果存在一个父节点就只有一个子节点，那么会将父节点和子节点合并。这样既可以减少存储空间，也可以提高查找效率。

Merkle tree

图片来自https://en.wikipedia.org/wiki/Merkle_tree

Merkle Tree，也叫哈希树 (hash tree)。叶子节点是数据块的hash值，而非叶节点是其对应子节点串联字符串的hash。

叶子节点，也就是最底层就是data blocks，将分块的数据（图中的L1 L2 L3 L4），分别计算hash。

非叶子节点，hash0-0由 hash（L1）得到，hash0-1由hash（L2）得到，那么hash0 则由hash（hash0-0   hash0-1）得到。由此往上计算，一直到root。

这样