❓什么是MPT树
- 结合了Patricia Trie （压缩前缀树）和 Merkle 树的特点，将中间节点的字符串换成哈希值，得到的就是一棵MPT树。
- 一句话总结就是：MPT树就是一棵带有hash验证功能的压缩前缀树
⭐️压缩前缀树的简单模拟
1. 节点种类
- leaf节点：路径的终点，包含nibble编码后剩余的key和完整的value
- extension节点：表示压缩的路径，和压缩前缀树中的压缩节点类似。
- branch节点：包含16个key槽和一个值槽，总共17个槽。每个槽用来存放下一个节点的hash。
2. nibble编码
用来对路径进行压缩编码，称为半字节编码，可以用来压缩key的长度。
3. RLP编码
用来对node和value进行编码，统一成字节数组。
4. hash编码
使用的是keccak-256算法，不是标准的SHA3。
5. 举例说明
假设我们要创建一个以太坊的状态树，存在key-value如下：
| key(地址) | value(账户状态) |
|---|---|
| 0x10a | V1 |
| 0x10b | V2 |
| 0x20c | V3 |
| 0x20d | V4 |
1. 对key进行nibble编码后找公共前缀：
找到公共前缀10,20
2. 构建extension节点和branch节点：
使用公共前缀可以建立10,20两个extension节点。每个extension节点只能指向一个branch节点。
3. 构建叶子节点：
叶子节点包含路径中剩余的key和完整的value
完成后的树结构：
🌏MPT树的特点
- 前缀共享：前缀树的特点，提供前缀共享能力。
- 路径压缩：压缩前缀树的特点，提供路径压缩，减少树高度。
- 默克尔验证：默克尔树的特点，提供确定的结构，和默克尔验证的能力。
- 插入删除查找高效：查找复杂度为O(n)
🌛MPT树的应用
- 以太坊的底层数据结构：以太坊的四棵树的底层数据结构都是MPT树（状态树、交易树、收据树、存储树）