以太坊MPT树节点分析

MPT树节点类型

参考：

叶节点：(valueNode)

  valueNode []byte

没有子节点，包括一个value，表示为[key,value]的键值对以太坊节点类型，其中key是key的特殊十六进制编码（HP编码）十六进制前缀编码

它实际上是字节数组 []byte 的别名，没有孩子。 在使用中，valueNode是携带数据的RLP哈希值，长度为32字节，将数据的RLP编码值作为valueNode的匹配项存储在数据库中。

扩展节点：（shortNode）

shortNode struct {
        Key   []byte
        Val   node
        flags nodeFlag
}

子节点只有一个，也是[key, value]的键值对以太坊节点类型，但是这里的value是其他节点的hash值，这个hash可以用来查询数据库中的节点。 也就是说，通过hash链接到其他节点。

分支节点（fullNode）：

fullNode struct {
        Children [17]node // Actual trie node data to encode/decode (needs custom encoder)
        flags    nodeFlag

}

包含 16 个分支和 1 个值。 因为MPT树中的key被编码成特殊的十六进制表示，加上最后一个值，分支节点是一个长度为17的列表，前16个元素对应key中16个可能的十六进制字符，如果有终止于该分支节点的[key,value]对，最后一个元素代表一个值，即分支节点可以是搜索路径的末端，也可以是路径的中间节点。

新增叶子节点和扩展节点！ （与前缀树相比）

这三种类型涵盖了普通 Trie（可能是 PatriciaTrie）的所有节点要求。 当任何[k,v]类型的数据被插入到一个MPT中时，它会以k字符串为路径沿着根向下延伸，在本次插入结束时首先会成为一个valueNode，k会从顶点开始root to the 节点终止的关键路径形式存在。 但是随着其他节点的不断插入和删除，根据MPT结构的要求，原来的节点可能会变成其他节点实现类型，同时MPT会不断变化或合并新的（parent）节点。

哈希节点：

hashNode  []byte

hashNode和valueNode一样，也是字符数组[]byte的别名，也是存储32byte的hash值，没有子节点。 不同的是hashNode是fullNode或者shortNode对象的RLP hash值，所以在用法上和valueNode有很大区别。

HashNode一般放在nodeFlag结构体中，由fullNode和shortNode间接持有。

// nodeFlag contains caching-related metadata about a node.
type nodeFlag struct {
    hash  hashNode // cached hash of the node (may be nil)
    gen   uint16   // cache generation counter
    dirty bool     // whether the node has changes that must be written to the database
}

一旦fullNode或shortNode的成员变量（包括子结构）发生变化，它们的hashNode就必须更新。 因此在trie.Trie结构体的insert()、delete()等函数的实现中，可以看到除了新建的fullNode和shortNode之外，子结构发生变化的fullNode和shortNode的nodeFlag成员也会也被重置。 hashNode 将被清除。 下次调用trie.Hash()时，自下而上遍历整个MPT时，所有清空的hashNode会被重新赋值。 这样在trie.Hash()结束后，我们就可以得到根节点root的一个hashNode，也就是此时MPT结构的hash值。

Header中的成员变量Root、TxHash、ReceiptHash的生成就来源于此。 显然，hashNode体现了MerkleTree的特点：每个父节点的hash值来自于所有子节点的hash值的组合，一个顶点的hash值可以代表一整个树结构。 hashNode加上前面的fullNode、shortNode、valueNode构成了一个完整的Merkle-PatriciaTrie结构。

树解析

用于添加、删除、检查和更改节点的函数都在trie.go 中定义。 在MPT的查找、插入、删除过程中，如果遍历遇到一个hashNode，首先需要从数据库中读取hash值为k的匹配v，然后解码还原v为fullNode或shortNode。 这个过程在代码中叫做resolve。

func (t *Trie) resolve(n node, prefix []byte) (node, error) {
    if n, ok := n.(hashNode); ok {
        return t.resolveHash(n, prefix)
    }
    return n, nil
}
func (t *Trie) resolveHash(n hashNode, prefix []byte) (node, error) {
    cacheMissCounter.Inc(1)
    hash := common.BytesToHash(n)
    if node := t.db.node(hash, t.cachegen); node != nil {
        return node, nil

    }
    return nil, &MissingNodeError{NodeHash: hash, Path: prefix}
}
// node retrieves a cached trie node from memory, or returns nil if none can be
// found in the memory cache.
func (db *Database) node(hash common.Hash, cachegen uint16) node {
    // Retrieve the node from cache if available
    db.lock.RLock()
    node := db.nodes[hash]
    db.lock.RUnlock()
    if node != nil {
        return node.obj(hash, cachegen)
    }
    // Content unavailable in memory, attempt to retrieve from disk
    enc, err := db.diskdb.Get(hash[:])

    if err != nil || enc == nil {
        return nil
    }
    return mustDecodeNode(hash[:], enc, cachegen)
}
func mustDecodeNode(hash, buf []byte, cachegen uint16) node {
    n, err := decodeNode(hash, buf, cachegen)
    if err != nil {
        panic(fmt.Sprintf("node %x: %v", hash, err))
    }
    return n
}
// decodeNode parses the RLP encoding of a trie node.
func decodeNode(hash, buf []byte, cachegen uint16) (node, error) {
    if len(buf) == 0 {

        return nil, io.ErrUnexpectedEOF
    }
    elems, _, err := rlp.SplitList(buf)
    if err != nil {
        return nil, fmt.Errorf("decode error: %v", err)
    }
    switch c, _ := rlp.CountValues(elems); c {
    case 2:
        n, err := decodeShort(hash, elems, cachegen)
        return n, wrapError(err, "short")
    case 17:
        n, err := decodeFull(hash, elems, cachegen)
        return n, wrapError(err, "full")
    default:
        return nil, fmt.Errorf("invalid number of list elements: %v", c)
    }
}

最后根据SplitList解出的节点个数判断decodeNode。 如果是2个，就是shortNode，如果是17个，就是fullnode。

如果一个fullNode本来只有两个子节点，现在要删除其中一个子节点，这个fullNode会退化成一个shortNode，如果剩下的子节点是shortNode，可以重新合并。