Merkle Patricia Trie(翻译)

原文:https://github.com/ethereum/wiki/wiki/Patricia-Tree

改良的 Merkle Patricia Trie 规范(又称为 Merkle Patricia Tree)

Merkle Patricia Trie(下简称 MPT 树,Trie 又称前缀树或字典树)尝试提供一种加密认证的数据结构,其可用于存储任意类型的的键值对。本文仅讨论键值对为字符串的情况(对于其他类型,只需要使用某种序列化方式将其转换为字符串即可)。这些键值对是完全确定的,这意味着两颗具有相同键值对的 Patricia 前缀树,它们的数据是保证完全一致的,因此也拥有相同的根哈希(root hash)。MPT 树提供优秀的 O(log(n)) 时间复杂度的插入,查询和删除性能。此外 MPT 树也比一些基于比较的替代方案(如红黑前缀树)更好理解和实现。

主要技术指标:Merkle Patricia Trie

但是,radix 树有一个较大的缺点:存储效率很低。举个例子,如果你只存储一个路径/值对,而这个路径长64个字符(32 字节的半字节(Hex)表示,正如以太坊的状态树一样),你将需要近 1K 的额外空间,一层一个字符地存储这个路径,并在需要删除它的时候花上整整 64 步。本文的 Patricia 树正是用来解决这个问题的。

改进

MPT 树通过提高原本的数据结构的复杂度,来尝试解决效率问题。MPT 树的节点可分为 4 种类型:

  1. NULL 空节点,用于表示空字符串
  2. branch 分支节点,具有 17 个项 [v0 ... v15, vt]
  3. leaf 叶子节点,具有 2 个项 [ encodedPath, value ]
  4. extension 扩展节点,具有 2 个项 [ encodedPath, key ]

在使用长为 64 个字符的路径的情况下,在遍历前缀树的前面几层的节点之后,后面层的节点很大可能都不再是发散的路径,而是一条单一路径。如果此时还按照前面的节点一样配置 index(Hex 字符集,共 16 个),则除了其中 1 个 index 不为空之外(即目标路径的下一个字符),剩余 15 个 index都是空的。这样做显然是不明智的。所以我们使用扩展节点 [ encodedPath, key ] 来快速处理这种单一路径。其中,encodePath 包含要跳过的”局部路径”(partial path,使用了下面提到的紧凑编码),key 用于下一次的数据库查询。

对于用 encodePath 第一个半字节就可以确定的叶子节点,上面提到的情况同样存在,且跳过的”局部路径”即完整路径的剩余部分。此时 value 即目标值。

当遍历半字节路径时,我们可能最终得到一个奇数个半字节的遍历路径。但因为所有的数据是以 bytes 格式存储的,因此不可能区分下面这种情况:半字节 1,和半字节 01 (两者都应该存储为 <01>)。所以如果要指定奇数长度,则在局部路径加上前缀标记。

规范:带可选终结符的十六进制序列的紧凑编码

上面提到,局部路径的首位半字节用于标记一个 2 项节点的属性:奇数剩余路径长度/偶数奇数剩余路径长度叶子节点/扩展节点 。定义如下:

对于偶数剩余路径长度(02),将始终跟随另一个“填充”的半字节 0

示例:

以下是在 MPT 树中获取节点的扩展代码:




没有评论


你先离开吧:)



发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据