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 项节点的属性：奇数剩余路径长度/偶数奇数剩余路径长度 和 叶子节点/扩展节点 。定义如下：

HEX 值 位值 | 节点局部路径类型 路径长度 ---------------------------------------------------------- 0 0000 | 扩展节点 偶数 1 0001 | 扩展节点 奇数 2 0010 | 终止节点 （叶子节点） 偶数 3 0011 | 终止节点 （叶子节点） 奇数

对于偶数剩余路径长度（0 或 2），将始终跟随另一个“填充”的半字节 0。

def compact_encode(hexarray): term = 1 if hexarray[-1] == 16 else 0 if term: hexarray = hexarray[:-1] oddlen = len(hexarray) % 2 flags = 2 * term + oddlen if oddlen: hexarray = [flags] + hexarray else: hexarray = [flags] + [0] + hexarray // hexarray now has an even length whose first nibble is the flags. o = '' for i in range(0,len(hexarray),2): o += chr(16 * hexarray[i] + hexarray[i+1]) return o

示例：

> [ 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] '20 0f 1c b8' > [ f, 1, c, b, 8, 10] '3f 1c b8'

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

def get_helper(node,path): if path == []: return node if node = '': return '' curnode = rlp.decode(node if len(node) < 32 else db.get(node)) if len(curnode) == 2: (k2, v2) = curnode k2 = compact_decode(k2) if k2 == path[:len(k2)]: return get_helper(v2, path[len(k2):]) else: return '' elif len(curnode) == 17: return get_helper(curnode[path[0]],path[1:]) def get(node,path): path2 = [] for i in range(len(path)): path2.push(int(ord(path[i]) / 16)) path2.push(ord(path[i]) % 16) path2.push(16) return get_helper(node,path2)