MPT树节点类型
参考：http://www.cocoachina.com/apple/20180921/24990.html
叶子节点:(valueNode)
valueNode []byte
没有子结点，包含一个value,表示为[key,value]的一个键值对，其中key是key的一种特殊十六进制编码(HP编码)十六进制前缀编码
它其实是字节数组[]byte 的一个别名，不带子节点。在使用中，valueNode 就是所携带数据部分的 RLP 哈希值，长度 32byte，数据的 RLP 编码值作为 valueNode 的匹配项存储在数据库里。
扩展节点:(shortNode)
shortNode struct {
Key []byte
Val node
flags nodeFlag
}
只有1个子结点,也是[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个value.因为MPT树中的key被编码成一种特殊的16进制的表示，再加上最后的value，所以分支节点是一个长度为17的list，前16个元素对应着key中的16个可能的十六进制字符，如果有一个[key,value]对在这个分支节点终止，最后一个元素代表一个值，即分支节点既可以搜索路径的终止也可以是路径的中间节点。
叶子节点和扩展节点是新增加的！（对比于前缀树来说）
这三种类型覆盖了一个普通 Trie(也许是 PatriciaTrie)的所有节点需求。任何一个[k,v]类型数据被插入一个 MPT 时，会以 k 字符串为路径沿着 root 向下延伸，在此次插入结束时首先成为一个 valueNode，k 会以自顶点 root 起到到该节点止的 key path 形式存在。但之后随着其他节点的不断插入和删除，根据 MPT 结构的要求，原有节点可能会变化成其他node 实现类型，同时 MPT 中也会不断裂变或者合并出新的(父)节点。
hashNode:
hashNode []byte
hashNode 跟 valueNode 一样，也是字符数组[]byte 的一个别名，同样存放 32byte 的哈希值，也没有子节点。不同的是，hashNode 是 fullNode 或者 shortNode 对象的 RLP 哈希值，所以它跟 valueNode 在使用上有着莫大的不同。
HashNode一般是放在nodeFlag这个struct中，被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结构的哈希值。
Header 中的成员变量 Root、TxHash、ReceiptHash 的生成，正是源于此。明显的，hashNode 体现了 MerkleTree 的特点：每个父节点的哈希值来源于所有子节点哈希值的组合，一个顶点的哈希值能够代表一整个树形结构。hashNode 加上之前的fullNode，shortNode，valueNode，构成了一个完整的 Merkle-PatriciaTrie 结构。
树的解析
节点增删查改用到的函数都定义于 trie.go。在 MPT 的查找，插入，删除过程中，如果在遍历时遇到一个 hashNode，首先需要从数据库里以这个哈希值为 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)
}
}
最后decodeNode就是根据SplitList解出来的node数量进行判断，如果是两个，则表示shortNode,如果是17个，则表示fullnode。
如果一个fullNode原本只有两个子节点，现在要删除其中一个子节点，那么这个fullNode就会退化为shortNode,同时保留的子节点如果是shortNode,还可以跟它再合并.
网友评论