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 种类型：
NULL空节点，用于表示空字符串branch分支节点，具有 17 个项[v0 ... v15, vt]leaf叶子节点，具有 2 个项[ encodedPath, value ]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)