https://blog.csdn.net/qq_33935254/article/details/55505472 图表
https://ethfans.org/toya/articles/588 更详细的可见此文章

综述

MPT是Ethereum自定义的Trie型数据结构。在代码中，trie.Trie结构体用来管理一个MPT结构，其中每个节点都是行为接口Node的实现类。

//trie/trie.go
type Trie struct {
    db           *Database
    root         node
    originalRoot common.Hash

    // Cache generation values.
    // cachegen increases by one with each commit operation.
    // new nodes are tagged with the current generation and unloaded
    // when their generation is older than than cachegen-cachelimit.
    cachegen, cachelimit uint16
}

下图是Trie结构体和node接口族的UML关系图：

image.png

实现

MPT的4种节点

type (
        //分支节点
    fullNode struct {
        Children [17]node // Actual trie node data to encode/decode (needs custom encoder)
        flags    nodeFlag
    }
        //叶子节点&扩展节点
    shortNode struct {
        Key   []byte
        Val   node
        flags nodeFlag
    }
    hashNode  []byte
    valueNode []byte
)

// EncodeRLP encodes a full node into the consensus RLP format.
func (n *fullNode) EncodeRLP(w io.Writer) error {
    return rlp.Encode(w, n.Children)
}

func (n *fullNode) copy() *fullNode   { copy := *n; return &copy }
func (n *shortNode) copy() *shortNode { copy := *n; return &copy }

// 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
}

• 在Trie结构体中，成员root始终作为整个MPT的根节点；originalRoot的作用是在创建Trie对象时承接入参hashNode；cacheGen是cache次数的计数器，每次Trie的变动提交后(写入的对象可由外部参数传入)，cacheGen自增1。Trie结构体提供包括对节点的插入、删除、更新，所有节点改动的提交(写入到传入参数)，以及返回整个MPT的哈希值。

node接口族担当整个MPT中的各种节点，node接口分四种实现: fullNode，shortNode，valueNode，hashNode，其中只有fullNode和shortNode可以带有子节点。

• fullNode 是一个可以携带多个子节点的父(枝)节点。它有一个容量为17的node数组成员变量Children，数组中前16个空位分别对应16进制(hex)下的0-9a-f，这样对于每个子节点，根据其key值16进制形式下的第一位的值，就可挂载到Children数组的某个位置，fullNode本身不再需要额外key变量；Children数组的第17位，留给该fullNode的数据部分。fullNode明显继承了原生trie的特点，而每个父节点最多拥有16个分支也包含了基于总体效率的考量。

• shortNode 是一个仅有一个子节点的父(枝)节点。它的成员变量Val指向一个子节点，而成员Key是一个任意长度的字符串(字节数组[]byte)。显然shortNode的设计体现了PatriciaTrie的特点，通过合并只有一个子节点的父节点和其子节点来缩短trie的深度，结果就是有些节点会有长度更长的key。

• valueNode 充当MPT的叶子节点。它其实是字节数组[]byte的一个别名，不带子节点。在使用中，valueNode就是所携带数据部分的RLP哈希值，长度32byte，数据的RLP编码值作为valueNode的匹配项存储在数据库里