MPT树的编码
参考:https://ethfans.org/posts/588
key值编码
1.RAW编码(原生编码)
Raw编码就是原生的key值，不做任何改变。这种编码方式的key，是MPT对外提供接口的默认编码方式。
例如一条key为“cat”，value为“dog”的数据项，其Raw编码就是['c', 'a', 't']，换成ASCII表示方式就是[63, 61, 74]
代码举例:
trie, _ = New(root, triedb)
_, err := trie.TryGet([]byte("120000"))
这个[]byte("120000")就是原生编码。
2.Hex编码(扩展的16进制编码)
我们在上篇文章介绍fullNode的时候，fullNode有个字段Children是17个node类型的数组。这样设计的目的是为了减少分支节点(fullNode)孩子(Children)的个数。因为一个原生编码中一个字节是8位，取值范围是[0-127),所以以太坊使用了一个新的单位叫nibble(4位）。取值范围是(0-15),这样一个分支节点的孩子至多只有16个。以太坊通过这种方式，减小了每个分支节点的容量，但是在一定程度上增加了树高。最后一个元素用来存储自身的内容。
这个转换的函数在encoding.go中。
func keybytesToHex(str []byte) []byte {
l := len(str)*2 + 1
var nibbles = make([]byte, l)
for i, b := range str {
nibbles[i*2] = b / 16
nibbles[i*2+1] = b % 16
}
nibbles[l-1] = 16
return nibbles
}
现在我们简单介绍下转换规则:
- 将Raw编码的每个字符，根据高4位低4位拆成两个字节；
- 若该Key对应的节点存储的是真实的数据项内容（即该节点是叶子节点），则在末位添加一个ASCII值为16的字符作为终止标志符;
- 若该key对应的节点存储的是另外一个节点的哈希索引（即该节点是扩展节点），则不加任何字符；
key为“cat”, value为“dog”的数据项，其Hex编码为[3, 15, 3, 13, 4, 10, 16]
3.HP编码(Hex-Prefix编码)
这个编码方式的目的是用于在磁盘存储的时候用的。通过上面Hex编码我们可以看到使用nibble方式的key的字节数比原生key多出了一倍。所以如果在数据库中使用这种编码就会浪费很多的空间。
我们看下encoding.go中的源码:
func hexToCompact(hex []byte) []byte {
terminator := byte(0)
if hasTerm(hex) {
terminator = 1
hex = hex[:len(hex)-1]
}
buf := make([]byte, len(hex)/2+1)
buf[0] = terminator << 5 // the flag byte
if len(hex)&1 == 1 {
buf[0] |= 1 << 4 // odd flag
buf[0] |= hex[0] // first nibble is contained in the first byte
hex = hex[1:]
}
decodeNibbles(hex, buf[1:])
return buf
}
// hasTerm returns whether a hex key has the terminator flag.
func hasTerm(s []byte) bool {
return len(s) > 0 && s[len(s)-1] == 16
}
func decodeNibbles(nibbles []byte, bytes []byte) {
for bi, ni := 0, 0; ni < len(nibbles); bi, ni = bi+1, ni+2 {
bytes[bi] = nibbles[ni]<<4 | nibbles[ni+1]
}
}
对着代码我们再介绍下HP编码规则:
- 若原key的末尾字节的值为16（即该节点是叶子节点），去掉该字节；(hasTerm)
- 在key之前增加一个半字节，其中最低位用来编码原本key长度的奇偶信息，key长度为奇数，则该位为1；低2位中编码一个特殊的终止标记符，若该节点为叶子节点，则该位为1；(buf[0] = terminator << 5)
- 若原本key的长度为奇数，则在key之前再增加一个值为0x0的半字节；
- 将原本key的内容作压缩，即将两个字符以高4位低4位进行划分，存储在一个字节中（Hex扩展的逆过程）(decodeNibbles)；
若Hex编码为[3, 15, 3, 13, 4, 10, 16]，则HP编码的值为[32, 63, 61, 74]
现在我们知道了三种编码方式，那他们三种方式的关系是怎样的呢？我们用一张图来表示：
转换关系
上面这张图很好的反映了三种编码之间的关系：
- RAW编码： 原生的key编码，是MPT对外提供接口中使用的编码方式，当数据项被插入到树中时，Raw编码被转换成Hex编码；
- Hex编码：16进制扩展编码，用于对内存中树节点key进行编码，当树节点被持久化到数据库时，Hex编码被转换成HP编码；
- HP编码：16进制前缀编码，用于对数据库中树节点key进行编码，当树节点被加载到内存时，HP编码被转换成Hex编码；
