以太坊源码阅读笔记-重要的数据结构：MPT

Trie树

字典树，单词查找树，前缀树

利用公共前缀来节约存储空间，但是如果前缀都不相同，将很耗内存

image.png

原理

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

Patricia Tries（前缀树）

Patricia Tries和Trie树的不同，就是如果

image.png

上面的图大家看左图和右上图就可以看出后者的优势

image.png

上图存储的8个Key Value对，可以看到前缀树的特点。

Key	value
6c0a5c71ec20bq3w	5
6c0a5c71ec20CX7j	27
6c0a5c71781a1FXq	18
6c0a5c71781a9Dog	64
6c0a8f743b95zUfe	30
6c0a8f743b95jx5R	2
6c0a8f740d16y03G	43
6c0a8f740d16vcc1	48

Merkle树 默克尔树

Merkle 又被成为hash数，其实就是把数据一层层的hash，最终形成一个hash

以太坊使用的是上面三种数据的结合体 MPT