如果一个基数树的“基数”(radix)为2或2的整数次幂,就被称为“帕特里夏树”,有时也直接认为帕特里夏树就是基数树
路径压缩的处理相当于实现了压缩前缀树的功能;不过路径表示是 Hex 字符串(nibbles),而存储却是以字节(byte)为单位的,这相当于浪费了一倍的存储空间
• > [ 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 树:
• ('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' ]