以太坊源码阅读笔记-重要的数据结构：MPT
2018-06-04 本文已影响24人
豆瓣奶茶
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
