专栏首页cwl_Java快速学习-帕特里夏树

快速学习-帕特里夏树

帕特里夏树(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' ]

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 3分钟速读原著《Java数据结构与算法》(三)

    cwl_java
  • 前端基础-CSS尺寸与行高属性

    取值:数字 + px/百分比/em -------------------------px代表像素,百分比代表浏览器宽度的百分比,em代表字符数

    cwl_java
  • 快速学习-Oozie的功能模块介绍

    cwl_java
  • 搞懂分布式技术6:Zookeeper典型应用场景及实践

    本系列文章将整理到我在GitHub上的《Java面试指南》仓库,更多精彩内容请到我的仓库里查看

    Java技术江湖
  • SQL学习笔记之B+树的几点总结

    本文主要以列表形式将B+树的特点以及注意点等列出来,主要参考《算法导论》、维基百科、各大博客的内容,结合自己的理解写的,如内容有不当之处,请各位雅正。

    Jetpropelledsnake21
  • 最短路问题与标号算法(label correcting algorithm)研究(6) - 扩展阅读

    这是全文第四章拓展阅读,也是全篇的最后一个章节。在前三章的内容里,我们详细介绍了最短路问题及其数学模型、最短路径求解算法以及单源、多源Label Correct...

    用户1621951
  • Godot3游戏引擎入门之五:上下左右移动动画(下)

    2018-10-11 by Liuqingwen | Tags: Godot | Hits

    IT自学不成才
  • 字典序???你是啥

    按字典序排列依次为1, 10, 11, 2, 3, 4, 5, 6, 7, 8, 9, 因此第4个数是2。

    不太灵光的程序员
  • etcd 集群大小迷思

    etcd 使用 raft 协议保证各个节点之间的状态一致。根据 raft 算法原理,节点数目越多,会降低集群的写性能。这是因为每一次写操作,需要集群中大多数节点...

    米开朗基杨
  • ZookeeperZNode基本命令四字命令SessionWatcherACLZookeeper集群Paxos算法ZAB协议Curator分布式锁

    在Zookeeper中,ZNode可以分为持久节点和临时节点两类。所谓持久节点是指一旦这个ZNode被创建了,除非主动进行ZNode的移除操作,否则这个ZNod...

    spilledyear

扫码关注云+社区

领取腾讯云代金券