以太坊的核心数据结构 - MPT树

❓什么是MPT树

• 结合了Patricia Trie （压缩前缀树）和 Merkle 树的特点，将中间节点的字符串换成哈希值，得到的就是一棵MPT树。
• 一句话总结就是：MPT树就是一棵带有hash验证功能的压缩前缀树

⭐️压缩前缀树的简单模拟

1. 节点种类

1. leaf节点：路径的终点，包含nibble编码后剩余的key和完整的value
2. extension节点：表示压缩的路径，和压缩前缀树中的压缩节点类似。
3. branch节点：包含16个key槽和一个值槽，总共17个槽。每个槽用来存放下一个节点的hash。

2. nibble编码

用来对路径进行压缩编码，称为半字节编码，可以用来压缩key的长度。

3. RLP编码

用来对node和value进行编码，统一成字节数组。

4. hash编码

使用的是keccak-256算法，不是标准的SHA3。

5. 举例说明

假设我们要创建一个以太坊的状态树，存在key-value如下：

1. 对key进行nibble编码后找公共前缀：

找到公共前缀10,20

2. 构建extension节点和branch节点：

使用公共前缀可以建立10,20两个extension节点。每个extension节点只能指向一个branch节点。

3. 构建叶子节点：

叶子节点包含路径中剩余的key和完整的value

完成后的树结构：

🌏MPT树的特点

1. 前缀共享：前缀树的特点，提供前缀共享能力。
2. 路径压缩：压缩前缀树的特点，提供路径压缩，减少树高度。
3. 默克尔验证：默克尔树的特点，提供确定的结构，和默克尔验证的能力。
4. 插入删除查找高效：查找复杂度为O(n)

🌛MPT树的应用

1. 以太坊的底层数据结构：以太坊的四棵树的底层数据结构都是MPT树（状态树、交易树、收据树、存储树）