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编码；