MPT樹節(jié)點(diǎn)類型

參考：http://www.cocoachina.com/apple/20180921/24990.html

葉子節(jié)點(diǎn):(valueNode)

  valueNode []byte

沒有子結(jié)點(diǎn)，包含一個value,表示為[key,value]的一個鍵值對，其中key是key的一種特殊十六進(jìn)制編碼(HP編碼)十六進(jìn)制前綴編碼

它其實(shí)是字節(jié)數(shù)組[]byte 的一個別名，不帶子節(jié)點(diǎn)。在使用中，valueNode 就是所攜帶數(shù)據(jù)部分的 RLP 哈希值，長度 32byte，數(shù)據(jù)的 RLP 編碼值作為 valueNode 的匹配項存儲在數(shù)據(jù)庫里。

擴(kuò)展節(jié)點(diǎn):(shortNode)

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

只有1個子結(jié)點(diǎn),也是[key，value]的一個鍵值對，但是這里的value是其他節(jié)點(diǎn)的hash值，這個hash可以被用來查詢數(shù)據(jù)庫中的節(jié)點(diǎn)。也就是說通過hash鏈接到其他節(jié)點(diǎn)。

分支節(jié)點(diǎn)(fullNode):

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

包含16個分支，以及1個value.因為MPT樹中的key被編碼成一種特殊的16進(jìn)制的表示，再加上最后的value，所以分支節(jié)點(diǎn)是一個長度為17的list，前16個元素對應(yīng)著key中的16個可能的十六進(jìn)制字符，如果有一個[key,value]對在這個分支節(jié)點(diǎn)終止，最后一個元素代表一個值，即分支節(jié)點(diǎn)既可以搜索路徑的終止也可以是路徑的中間節(jié)點(diǎn)。

葉子節(jié)點(diǎn)和擴(kuò)展節(jié)點(diǎn)是新增加的！（對比于前綴樹來說）

這三種類型覆蓋了一個普通 Trie(也許是 PatriciaTrie)的所有節(jié)點(diǎn)需求。任何一個[k,v]類型數(shù)據(jù)被插入一個 MPT 時，會以 k 字符串為路徑沿著 root 向下延伸，在此次插入結(jié)束時首先成為一個 valueNode，k 會以自頂點(diǎn) root 起到到該節(jié)點(diǎn)止的 key path 形式存在。但之后隨著其他節(jié)點(diǎn)的不斷插入和刪除，根據(jù) MPT 結(jié)構(gòu)的要求，原有節(jié)點(diǎn)可能會變化成其他node 實(shí)現(xiàn)類型，同時 MPT 中也會不斷裂變或者合并出新的(父)節(jié)點(diǎn)。

hashNode:

hashNode  []byte

hashNode 跟 valueNode 一樣，也是字符數(shù)組[]byte 的一個別名，同樣存放 32byte 的哈希值，也沒有子節(jié)點(diǎn)。不同的是，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 的成員變量(包括子結(jié)構(gòu))發(fā)生任何變化，它們的 hashNode 就一定需要更新。所以在 trie.Trie 結(jié)構(gòu)體的 insert()，delete()等函數(shù)實(shí)現(xiàn)中，可以看到除了新創(chuàng)建的 fullNode、shortNode，那些子結(jié)構(gòu)有所改變的 fullNode、shortNode 的 nodeFlag 成員也會被重設(shè)，hashNode 會被清空。在下次 trie.Hash()調(diào)用時，整個 MPT 自底向上的遍歷過程中，所有清空的 hashNode 會被重新賦值。這樣trie.Hash()結(jié)束后，我們可以得到一個根節(jié)點(diǎn) root 的 hashNode，它就是此時此刻這個 MPT結(jié)構(gòu)的哈希值。

Header 中的成員變量 Root、TxHash、ReceiptHash 的生成，正是源于此。明顯的，hashNode 體現(xiàn)了 MerkleTree 的特點(diǎn)：每個父節(jié)點(diǎn)的哈希值來源于所有子節(jié)點(diǎn)哈希值的組合，一個頂點(diǎn)的哈希值能夠代表一整個樹形結(jié)構(gòu)。hashNode 加上之前的fullNode，shortNode，valueNode，構(gòu)成了一個完整的 Merkle-PatriciaTrie 結(jié)構(gòu)。

樹的解析

節(jié)點(diǎn)增刪查改用到的函數(shù)都定義于 trie.go。在 MPT 的查找，插入，刪除過程中，如果在遍歷時遇到一個 hashNode，首先需要從數(shù)據(jù)庫里以這個哈希值為 k，讀取出相匹配的v，然后再將 v 解碼恢復(fù)成 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就是根據(jù)SplitList解出來的node數(shù)量進(jìn)行判斷，如果是兩個，則表示shortNode,如果是17個，則表示fullnode。

如果一個fullNode原本只有兩個子節(jié)點(diǎn)，現(xiàn)在要刪除其中一個子節(jié)點(diǎn)，那么這個fullNode就會退化為shortNode,同時保留的子節(jié)點(diǎn)如果是shortNode,還可以跟它再合并.