梅克尔-帕特里夏树 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）

基数树又叫压缩前缀树（compact prefix tree），是一种空间优化后的字典树，其中如果一个节点只有唯一的子节点，那么这个子节点就会与父节点合并存储

基数树节点

在一个标准的基数树里，每个节点存储的数据如下：[i0, i1, … in, value]

• 这里的 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 次下探访问。

梅克尔树（Merkel Tree）

也被称作哈希树（Hash Tree），以数据块的 hash 值作为叶子节点存储值。梅克尔树的非叶子节点存储其子节点内容串联拼接后的 hash 值。