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

快速学习-梅克尔-帕特里夏树

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 大数据-Linux环境配置

    scp /root/.ssh/authorized_keys node02:/root/.ssh

    cwl_java
  • 快速学习-帕特里夏树

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

    cwl_java
  • 快速学习-什么是分布式文件系统

    分布式文件系统解决了海量文件存储及传输访问的瓶颈问题,对海量视频的管理、对海量图片的管理等。

    cwl_java
  • 图解精选 TOP 面试题 004 | LeetCode 108. 将有序数组转换为二叉搜索树

    本题中,一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

    江不知
  • 如何进入PageAdmin安装界面

    一般下面几个应用场景如第一次使用PageAdmin配置参数、服务器迁移、主域名更换、忘记超级管理员密码等都可以在安装界面进行设置,通过修改配置文件可以进入重装界...

    用户5258701
  • 使用SVG symbols建立图标系统完整指南

    从最开始的使用img图片,到后来的使用css sprite来减少服务器请求,再到流行的图形字体化图标Iconfont。现在,一种全新的图标使用方式开始流行了起来...

    用户6167509
  • 基础知识 | R语言绘图基础之柱形图

    在视觉性吸引方面,人类绝对是动物界的另类。当一张一张数据分析的统计表摆在眼前时,人们并不能快速的洞察其中的关系。然而,当一张张精心绘制图形展现零散数据时,...

    黑妹的小屋
  • 巧用R语言生成建模所需的测试数据

    set.seed(n)主要是为了重复生成相同的随机数,特别用于重复性验证。只要在使用函数生成随机数之前设定set.seed(n),即可生成相同的随机数。

    1480
  • 如何进入PageAdmin安装界面

    一般下面几个应用场景如第一次使用PageAdmin配置参数、服务器迁移、主域名更换、忘记超级管理员密码等都可以在安装界面进行设置,通过修改配置文件可以进入重装界...

    用户5258701
  • 如何进入PageAdminCMS安装界面

    一般下面几个应用场景如第一次使用PageAdmin配置参数、服务器迁移、主域名更换、忘记超级管理员密码等都可以在安装界面进行设置。

    Almost Lover

扫码关注云+社区

领取腾讯云代金券