快速学习-帕特里夏树

帕特里夏树（Patricia Tree）

如果一个基数树的“基数”（radix）为2或2的整数次幂，就被称为“帕特里夏树”，有时也直接认为帕特里夏树就是基数树

• 以太坊中采用 Hex 字符作为 key 的字符集，也就是基数为16 的帕特里夏树
• 以太坊中的树结构，每个节点可以有最多 16 个子节点，再加上 value，所以共有 17 个“插槽”（slot）位置
• 以太坊中的帕特里夏树加入了一些额外的数据结构，主要是为了解决效率问题

MPT（Merkel Patricia Tree）

• 梅克尔-帕特里夏树是梅克尔树和帕特里夏树的结合
• 以太坊中的实现，对 key 采用 Hex 编码，每个 Hex 字符就是一个nibble（半字节）
• 遍历路径时对一个节点只访问它的一个 nibble ，大多数节点是一个包含17个元素的数组；其中16个分别以 hex字符作为索引值，存储路径中下一个 nibble 的指针；另一个存储如果路径到此已遍历结束，需要返回的最终值。这样的节点叫做“分支节点”（branch node）
• 分支节点的每个元素存储的是指向下一级节点的指针。与传统做法不同，MPT 是用所指向节点的 hash 来代表这个指针的；每个节点将下个节点的 hash 作为自己存储内容的一部分，这样就实现了 Merkel 树结构，保证了数据校验的有效性

MPT 节点分类

MPT 中的节点有以下几类：

• 空节点（NULL）
• 表示空字符串
• 分支节点（branch）
• 17 个元素的节点，结构为 [ v0 … v15, vt ]
• 叶子节点（leaf）
• 拥有两个元素，编码路径 encodedPath 和值 value
• 扩展节点（extension）
• 拥有两个元素，编码路径 encodedPath 和键 key

MPT 中数据结构的优化

• 对于64个字符的路径长度，很有可能在某个节点处会发现，下面至少有一段路径没有分叉；这很难避免
• 我们当然可以依然用标准的分支节点来表示，强制要求这个节点必须有完整的16个索引，并给没有用到的那15个位置全部赋空值；但这样有点蠢
• 通过设置“扩展节点”，就可以有效地缩短访问路径，将冗长的层级关系压缩成一个键值对，避免不必要的空间浪费
• 扩展节点（extension node）的内容形式是 [encodedPath, key]，其中 encodedPath 包含了下面不分叉的那部分路径，key 是指向下一个节点的指针（hash，也即在底层db中的存储位置）
• 叶子节点（leaf node）：如果在某节点后就没有了分叉路径，那这是一个叶子节点，它的第二个元素就是自己的 value

压缩之后的 ”dog” 路径

在这里插入图片描述

紧凑编码（compact coding）

路径压缩的处理相当于实现了压缩前缀树的功能；不过路径表示是 Hex 字符串（nibbles），而存储却是以字节（byte）为单位的，这相当于浪费了一倍的存储空间

• 我们可以采用一种紧凑编码（compact coding）方式，将两个 nibble 整合在一个字节中保存，这就避免了不必要的浪费
• 这里就会带来一个问题：有可能 nibble 总数是一个奇数，而数据总是以字节形式存储的，所以无法区分 nibble 1 和nibbles 01；这就使我们必须分别处理奇偶两种情况
• 为了区分路径长度的奇偶性，我们在 encodedPath 中引入标识位

Hex 序列的压缩编码规则

• 我们在 encodedPath 中，加入一个 nibble 作为前缀，它的后两位用来标识节点类型和路径长度的奇偶性

在这里插入图片描述

• MPT 中还有一个可选的“结束标记”（用T表示），值为0x10 (十进制的16)，它仅能在路径末尾出现，代表节点是一个最终节点（叶子节点）
• 如果路径是奇数，就与前缀 nibble 凑成整字节；如果是偶数，则前缀 nibble 后补 0000 构成整字节

编码示例

• > [ 1, 2, 3, 4, 5, ...] 不带结束位，奇路径
• '11 23 45' 
• > [ 0, 1, 2, 3, 4, 5, ...] 不带结束位，偶路径
• '00 01 23 45' 
• > [ 0, f, 1, c, b, 8, 10] 带结束位 T 的偶路径
• '20 0f 1c b8' 
• > [ f, 1, c, b, 8, 10] 带结束位 T 的奇路径
• '3f 1c b8'

MPT 树结构示例

• 假设我们现在要构建一个存储了以下键值对的 MPT 树：

• ('do', 'verb'), ('dog', 'puppy'), ('doge', 'coin'), ('horse', 'stallion')

• 首先我们会把所有的路径（path）转成 ASCII 码表示的 bytes： • <64 6f> : ‘verb’

• <64 6f 67> : 'puppy' 
• <64 6f 67 65> : 'coin' 
• <68 6f 72 73 65> : 'stallion‘

• 然后我们就可以用在底层db中存储的以下键值对，构建出 MPT 树：

• rootHash: [ <16>, hashA ] 
• hashA: [ <>, <>, <>, <>, hashB, <>, <>, <>, hashC, <>, <>, <>, <>, <>, <>, <>, <> ] 
• hashC: [ <20 6f 72 73 65>, 'stallion' ] 
• hashB: [ <00 6f>, hashD ] 
• hashD: [ <>, <>, <>, <>, <>, <>, hashE, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'verb' ] 
• hashE: [ <17>, hashF ] 
• hashF: [ <>, <>, <>, <>, <>, <>, hashG, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'puppy' ] 
• hashG: [ <35>, 'coin' ]

在这里插入图片描述