梅克尔-帕特里夏树 Merkel-Patricia Tree（MPT）
MPT是什么
- Merkel Patricia Tree (MPT)，翻译为梅克尔-帕特里夏树
- MPT 提供了一个基于密码学验证的底层数据结构，用来存储键值对（key-value）关系
- MPT 是完全确定性的，这是指在一颗 MPT 上一组键值对是唯一确定的，相同内容的键可以保证找到同样的值，并且有同样的根哈希（root hash）
- MPT 的插入、查找、删除操作的时间复杂度都是O(log(n))，相对于其它基于复杂比较的树结构（比如红黑树），MPT 更容易理解，也更易于编码实现
从字典树（Trie）说起
- 字典树（Trie）也称前缀树（prefix tree），属于搜索树，是一种有序的树数据结构
- 字典树用于存储动态的集合或映射，其中的键通常是字符串
快速学习-梅克尔-帕特里夏树
基数树（Radix Tree）
基数树节点
- 这里的 i0,i1,…,in 表示定义好的字母表中的字符，字母表中一共有n+1个字符，这颗树的基数（radix）就是 n+1
- value 表示这个节点中最终存储的值
- 每一个 i0 到 in 的“槽位”，存储的或者是null，或者是指向另一节点的指针
- 用节点的访问路径表示 key，用节点的最末位置存储value，这就实现了一个基本的键值对存储
示例
- 我们有一个键值对{ “dog”: “puppy” }，现在希望通过键 dog 访问它的值；我们采用16进制的 Hex 字符作为字符集
- 首先我们将 “dog” 转换成 ASCII 码，这样就得到了字符集中的表示 64 6f 67，这就是树结构中对应的键
- 按照键的字母序，即 6->4->6->f->6->7，构建树中的访问路径
- 从树的根节点（root）出发，首先读取索引值（index）为 6 的插槽中存储的值，以它为键访问到对应的子节点
- 然后取出子节点索引值为 4 的插槽中的值，以它为键访问下一层节点，直到访问完所需要的路径
- 最终访问到的叶子节点，就存储了我们想要查找的值，即“puppy”
快速学习-梅克尔-帕特里夏树
基数树的问题
数据校验
- 基数树节点之间的连接方式是指针，一般是用32位或64位的内存地址作为指针的值，比如C语言就是这么做的。但这种直接存地址的方式无法提供对数据内容的校验，而这在区块链这样的分布式系统中非常重要。
访问效率
-
基数树的另一个问题是低效。如果我们只想存一个 bytes32 类型的键值对，访问路径长度就是64（在以太坊定义的 Hex 字符
集下）；每一级访问的节点都至少需要存储 16 个字节，这样就需要至少 1k 字节的额外空间，而且每次查找和删除都必须完整
地执行 64 次下探访问。