Ethereum MPT 简介

[winterpi]

MPT （Merkle Patricia Trie / Merkle Patricia Tree）

• 它是 Merkle Tree 与 Patricia Tree 的混合物;
• Merkle Tree 用于保证数据安全;
• Patricia Tree 用于提升树的读写效率。

Trie 字典树

• Trie 的发明者Edward Fredkin把它读作/ˈtriː/ “tree”。但是，其他作者把它读作/ˈtraɪ/ “try”
• 常用于统计和排序大量的字符串，查询效率高；

Patricia Tree（压缩前缀树/基数树）

• 相对于 Trie，缩小了存储空间，提升了查询效率。

Ethereum MPT 改进方案

• 对 Patricia Tree 进一步改进，提高效率、降低树的深度、减少 IO 次数；

改进的方案，提出 4 种节点：

1. 空白节点 NULL
2. 分支节点 branch node
3. 叶子节点 leaf node
4. 扩展节点 extension node

参考：

1. 以太坊源码分析--MPT树
2. Ethereum MPT（Merkle Patricia Tries）详解