引言

MPT 树（Merkle Patricia Tree）是以太坊中一种非常重要的数据结构，用来存储用户账户的状态及其变更（ 状态树 ）、交易信息（ 交易树 ）、交易的收据信息（ 收据树 ）。它实际上是Merkle Tree 和Patricia Tree组合而成的一种树形结构，并且同时具备这两种树的特性和优点。我们期望从原理和源代码两方面入手，以期对其进行深入的了解。

实现原理

以Patricia Tree为基础，以太坊主要从以下几个方面对其进行了改进和优化。

使用 []byte 作为 key 的类型，而非字符串

在以太坊的 Trie 模块中，key 和 value 都是 []byte 类型。如果要使用其它类型，需要将其转换成[]byte 类型（比如使用rlp 进行转换）。当然这不是什么本质上改变，我个人感觉只是为了编码方便吧。因为 rlp 模块可以方便的把各种结构序列化成 []byte 而不是 string。

nibble: key 类型的最小单位

其实在以太坊的 Trie 模块对外提供的接口中，key 类型当然是 []byte。但在内部实现里，将 key 中的每个字节按高 4 位和低 4 位拆分成了两个字节。比如你传入的 key 是：

[0x1a, 0x2b, 0x3c, 0x4d]

Trie 内部将这个 key 拆分成：

[0x1, 0xa, 0x2, 0xb, 0x3, 0xc, 0x4, 0xd]

Trie 内部的编码中将拆分后的每一个字节称为nibble

如果使用一个完整的 byte 作为 key 的最小单位，那么前文提到的索引数组的大小应该是 256（byte 作为数组的索引，最大值为 255，最小值为 0）。而索引数组的每个元素都是一个 32 字节的哈希（这在下一条中进行了说明）, 这样每个结点要占用大量的空间。并且索引数组中的元素多数情况下是空的，不指向任何结点。因此这种实现方法占用大量空间而不使用。以太坊的改进方法，可以将索引数组的大小降为 16（4 个 bit 的最大值为 0xF，最小值为 0），因此大大减少空间的浪费。

使用 hash 引用结点而不是内存指针

在以太坊的实现中，索引数组的每个元素都是下一个结点的 hash，而非指针。也就是说，父结点持有的是子结点的 hash。

这种实现方式使得以太坊中的 Trie 带有了默克尔树的功能：如果两个 Trie 的根结点的 hash 相同，我们就可以断定，这两棵树的内容完全一样。

需要注意的是，这种实现也包括对 value 的引用。也就是说在以太坊的 Trie 中，遍历到叶子结点以后得到的是 value 的 hash，而非 value 本身。使用这个 hash 从数据库中读取出来的值才是 value。

当树的某条路径没有分支时，使用一个结点存储路径上的所有 key

我们回看上面介绍字典树的那张图，其中 "medicine" 这条路径中，除了前三个字符 'med'，其它字符都没有分支，因此为了节省空间，以太坊将这种情况下的结点缩减为一个。如下图所示：

这样就可以进一步节省空间的开销。但同时也产生了一个问题：对于某个结点，如何知道它存储的是索引数组，还是 key 的数组呢？

以太坊解决这个问题的方式是通过结点元素个数的不同进行区分。以太坊在 Trie 内部将结点分成了两类：全节点（fullNode）和快捷节点（shortNode）。全节点有 17 个元素，而快捷结点有两个元素。它们的示意表达如下：

全结点： [i0, i2, ... i15, value]
快捷结点：[[k0, k1, ... kn], value ]

可以看到全结点由索引数组（共 16 个元素）和一个 value 组成（前面说过 value 的引用也是通过 hash，而不是直接存储 value 的值）；而快捷结点有 2 个元素，一个是 key 数组，另一个就是 value。

此时虽然可以知道一个结点存储的数据的格式，但对于快捷结点，仍有两个问题没有解决。

一个问题是，前面说过 key 的最小单位是 nibble，。那么如果在快捷结点中 nibble 的个数是奇数，它重新组合成 []byte 存储就会有麻烦。比如

nibbles: 0x1 0xa 0x2 0xb 0x3\
组合成[]byte？ 0x1a 0x2b 0x30 还是 0x01 0xa2 0xb3

可见无论怎么组合，都会有多写入一个无效的 nibble。等再解析的时候，我们怎么知道哪个是无效的呢？

另一个问题是，我们该如何解析快捷结点中的 value 所代表的数据。它是代表真正的 value 数据，还是另一个结点？

这两个问题存在的原因在于，Trie 中的结点是需要进行数据库存取的。如果只是在内存中，这两个问题不会存在：只在内存中没有必要把 nibble 组成的 key 变成 []byte 类型；通过数据的结构体类型也很容易知道 value 所代表的数据类型。但要将快捷结点存入数据库中，需要将 nibble 组成的 key 变成[]byte 存储（其实也可以直接存储 nibble 数组，只是多占了一倍空间）；而从数据库中读取 value 所代表的数据时，需要知道是将其解析成一个新的结点，还是仅代表 value 原始值无需解析。

有问题就要解决。既然问题产生于数据库的存取，很自然地我们会想到，可以在存的时候加上一些信息，能标识出哪一位是无效的 nibble，和 value 所代表的数据类型。当从数据库中取的时候，就可以根据这些信息将数据恢复啦。

是的，解决的思路都是类似的，只是实现方法千千万。以太坊的实现方法是在存入数据库时，将 nibble 组合成的 []byte 值的第 0 个字节的高 4 位作为信息存储位而不存储真正的 nibble 字节。可以说这种方法真是一点内存都不浪费。

那么第 0 个字节的高 4 位是怎么组织的呢？目前我们有两个信息需要存储：

• nibble 的个数的奇偶信息
• value 代表结点还是真正的 value 数据

可以看到这俩个信息都是二元的（非此即彼），因此有 2 个 bit 就可以了。以太坊的做法是第 0 位存储奇偶信息，第 1 位存储 value 代表的类型。具体信息如下：

可以看到当 nibble 个数为偶数时，第 0 个字节的低 4 位总是无效的；但为奇数时，低 4 位是有效的，其值为第一个 nibble。

让我们通过例子来确认对这些描述的理解。以下示意的都是快捷结点：

[ [0xa, 0xb, 0xc, 0xd, 0xe], value_node ]  // 奇数个nibble，value代表node  
编码： 0x1a 0xbc 0xde

[ [0xa, 0xb, 0xc, 0xd], value_node ] //偶数个nibble，value代表node  
编码： 0x00 0xab 0xcd  

[ [0xa, 0xb, 0xc, 0xd, 0xe], value_data ] //奇数个nibble，value代表数据  
编码： 0x3a 0xbc 0xde  

[ [0xa, 0xb, 0xc, 0xd], value_data ]  //偶数个nibble，value代表数据  
编码： 0x20 0xab 0xcd

需要再强调一下的是，这个编码方法只有在数据库存取的时候才用到。在读到内存中以后，nibble 是直接以 []byte 类型存储的（虽然每个 byte 的最大值是 15）, 且如果 value 代表的是数据则在 nibble 数组的最后 append 值 16（注意 16 是一个无效的 nibble 值，因此可以和正常的 nibble 值作区分），代码中根据最后一个值是否是 16 判断 value 的类型。

另外虽然我们一直没有明确说明，但上面在说 value 代表的类型的时候，我们其实是在判断当前结点是不是叶子结点：如果是叶子结点，value 当然代表数据；如果不是，value 也当然代表一个 node。

至此，所有问题都已解决，终于可以正常的将多个没有分支的结点压缩到一个结点存储了（为了解决一个问题，引入了好几个问题）。

我们来总结一下我们当前讨论的改进：以太坊通过以下方式，减少无分支路径上的结点数：

• 将结点类型分成了 fullNode 和 shortNode，shortNode 存储多个 key 的 nibble
• 使用第 0 个字节的高 4 位编码，标识 nibble 的奇偶个数（也即第 0 个字节的低 4 位是否是有效的 nibble）和 value 类型（也即当前结点是否是叶子结点）

内部节点引用计数

这一改进其实与 trie 原理本身没有关系，但我认为也是非常重要的，因此有必要在这里介绍一下。

在 trie 模块中，有一个Database对象，你可以理解为它是底层数据库的一个缓存层。在实际使用过程中，Trie对象就把Database作为数据库使用。但Database的重要功能不在于缓存，而在于缓存时对节点数据进行了引用计数，并提供了Database.Reference和Database.Dereference来引用和解引用某个 trie 节点。如果某个节点的引用计数变为 0，则该节点将被从内存中删除，因而也不会被写入到真正的数据库中。

注意Database中只对内存中缓存的节点进行了引用计数，已经写入数据库的节点没有引用计数数据。

以太坊的 trie 模块为什么对 trie 作了这么一个改进呢？这主要是为了解决以太坊数据存储的问题。随着以太坊的长时间运行，以太坊数据已经非常大且仍在以类似指数的速度增长。增长的主要数据，就是以太坊的账户状态（state）信息，而以太坊 trie 作为 state 的底层数据组织方式，它的实现决定了这种增长速度。因为在以太坊中，每生成一个新的区块，不会直接修改上一个区块的 state 数据，而是类似于“写时复制”的机制，将数据修改后重新存储一份，对于 trie 来说则是生成新的子节点进行存储，如下图所示：

以上图为例，只要修改账户 X 的信息，就需要新增 4 个节点而不会修改原来的节点（实际情况可能不止 4 个），这就是 state 数据增长如此之快的原因。为了减轻数据存储的压力，以太坊提出了修剪区块（pruned
block）的概念，即利用 trie 模块中的trie.Database对缓存节点进行引用计数，并在 blockchain 模块中进行相应的引用和解引用操作。如此释放了大量不需要保存的历史数据的存储空间。（关于区块修剪可以参考 这里 ）

特性

从上面介绍的所有改进我们可以了解到，以太坊的实现非常节省内存。另一个重要的改进是，它与默克尔树进行了融合，在可以高效存取 (key,value) 对的同时，还具有默克尔树的特性：通过比较两个 Trie 对象的根结点的 hash，就可以判断这两棵树是否存储了相同的内容。

默克尔树的这一特性是非常有用的。在以太坊中，Trie 用来存储四种对象：

• State
• Storage
• Transactions
• Receipts

现在我们可以不必理会这些对象的意义（其实我现在也不是全部了解），但它们在 Trie 这一层面都是类似的，我们以 State 举例。以太坊的 State 存储了区块上所有账号的信息，包括账户余额等。这些账号信息随着区块的变化而变化。在即将打包一个新的区块时，以太坊会更新代表 State 的 Trie 对象，并将更新后的 Trie 根结点 hash 写入新的区块头中。当其它运行以太坊节点的机器收到这个区块时，它可以根据上一个区块中的 State 信息，加上新块区的变动后，将得到的 Trie 的根结点 hash 与区块头中的进行比较。如果 hash 一致，则这个区块的 State 信息就得到了承认。

源码分析

以太坊 trie 模块位于项目目录下的 trie 目录。下面我们先学习下模块导出的功能和用法，然后结合源代码介绍一下目录的组织结构和框架。

trie 模块使用方法

trie 模块提供了四个主要的对象和接口：Trie、SecureTrie、NodeIterator、TrieSync、Database。下面分别介绍。

Trie

Trie 对象实现了 Merkle Patricia Tree 的全部功能，包括(key,value) 对的增删改查、计算默克尔哈希，以及将整个树写入数据库中。

你可以使用 trie.New 或 trie.NewTrieWithPrefix 来创建或打开一个 Trie 对象。trie.NewTrieWithPrefix 相对于 trie.New 的不同之处在于，你需要提供一个前缀串，每次查询或写入 (key,value) 对时，都会自动将这个前缀串加到 key 的前面，然后再执行相应操作。

Trie 对象提供的方法名都很简洁易懂，几乎所有方法都可以根据名字知道其功能。这里我们只是简单罗列一下，不一一详细说明。

• func (t *Trie) NodeIterator(start []byte) NodeIterator
• func (t *Trie) PrefixIterator(prefix []byte) NodeIterator
• func (t *Trie) Get(key []byte) []byte
• func (t *Trie) TryGet(key []byte) ([]byte, error)
• func (t *Trie) Update(key, value []byte)
• func (t *Trie) TryUpdate(key, value []byte)
• func (t *Trie) Delete(key []byte)
• func (t *Trie) TryDelete(key []byte) error
• func (t *Trie) Root() []byte
• func (t *Trie) Hash() common.Hash
• func (t *Trie) Commit() (root common.Hash, err error)
• func (t *Trie) CommitTo(db DatabaseWriter) (root common.Hash, err error)
• func (t *Trie) SetCacheLimit(l uint16)
• func (t *Trie) Prove(key []byte, fromLevel uint, proofDb DatabaseWriter) error

SecureTrie

SecureTrie 对象实现了 Trie 相同的功能，实际上它内部几乎都是调用 Trie 对象的方法实现的。唯一不同的是，SecureTrie 中的所有方法会将传入的 key 计算一个哈希，然后把这个哈希当作 key 进行操作。因此你无法通过根结点到叶子结点的路径上的信息拼凑出 key 的内容，这也是它叫作 "Secure" 的原因。

SecureTrie 提供的方法与 Trie 类似，这里不再细说。唯一需要注意的是，对SecureTrie节点进行枚举时，想要获取原始的 key 值，需要多调用一步SecureTrie.GetKey。因为NodeIterator.LeafKey和Iterator.Key得到的是加密后的 key，需要调用SecureTrie.GetKey得到原始 key。

NodeIterator

NodeIterator 是一个接口，如名字所示，它提供了遍历树内部所有结点的功能。它提供的方法如下：

• func (it NodeIterator) Next(bool) bool\
• func (it NodeIterator) Error() error\
• func (it NodeIterator) Hash() common.Hash\
• func (it NodeIterator) Parent() common.Hash\
• func (it NodeIterator) Path() []byte\
• func (it NodeIterator) Leaf() bool\
• func (it NodeIterator) LeafBlob() []byte\
• func (it NodeIterator) LeafKey() []byte

NodeIterator 的核心是 Next 方法，每调用一次这个方法，NodeIterator 对象当前代表的结点就会更新至下一个结点，此时你可以调用其它方法获取这个结点的信息。当所有结点遍历结束，Next 方法返回 false。所以使用 NodeIterator 接口的代码一般形式都像这样：

for it.Next(true) {
... // 现在it代表一了一个新的结点，你可以调用其它方法如it.Hash等，获取这个结点的信息
}

需要注意的是，NodeIterator 接口对结点的遍历是有序的。其实 Trie 就是一棵有序树，而遍历的内部实现就是按照 Key 从短到长、从小到大的顺序进行的。（然而貌似并没有文档写明并保证遍历是有序的）

生成 NodeIterator 结口的方法有 3 种。我们分别说明一下。

1. 调用和 Trie.NodeIterator 或 Trie.PrefixIterator

如果你想遍历某个 Trie 对象的所有结点，可以调用 Trie 对象的方法NodeIterator()或PrefixIterator()，这俩个方法都返回一个 NodeIterator 接口用来进行遍历。NodeIterator() 的 start 参数可以让你有选择的指定从哪个路径开始遍历，如果为 nil 则从头到尾按顺序遍历。PrefixIterator() 方法能过参数指定前缀后，其返回的 NodeIterator 接口只会遍历路径中包含了你指定前缀的结点。

2. 调用 NewDifferenceIterator

NewDifferenceIterator函数的功能如名字所示，只遍历不同的部分。当你调用 NewDifferenceIterator(a,
b NodeIterator) 后，生成的 NodeIterator 只遍历存在于 b 但不存在于 a 中的结点。

3. 调用 NewUnionIterator

NewUnionIterator也如名字所示，会把多个 NodeIterator 当成一个合集进行遍历。当你调用 NewUnionIterator(its
[]NodeIterator)后，生成的 NodeIterator 遍历的结点是所有传入的结点的合集。

另外我们不得不强调一下 NewIterator 函数，因为我觉得这个函数更常用到。这个函数用来枚举树中的所有 (key,
value) 对，而不是每个结点（多数情况下我们并不关心中间结点的数据）。这个函数声明如下：

func NewIterator(it NodeIterator) *Iterator

它并不返回 NodeIterator，而是返回 Iterator 指针对象。Iterator 是一个结构体，只有一个方法。定义如下：

type Iterator struct {
nodeIt NodeIterator

Key   []byte // Current data key on which the iterator is positioned on
Value []byte // Current data value on which the iterator is positioned on
Err   error
}

//Iteartor的Next方法
func (it *Iterator) Next() bool

可以看到 Iterator 结构体导出了 Key、Value、Err 三个字段。每调用一次 Next 方法，Key、Value 和 Err 字段就会被更新。以下是一段使用 NewIterator 的示例：

//假设tr是一个Trie变量，并且包含了("hi", "lili"), ("hello", "world"), ("good", "morning")三对数据
it := trie.NewIterator(tr.NodeIterator(nil))
for it.Next {
if it.Err != nil {
fmt.Println(it.Err)
continue
}
fmt.Println(it.Key, it.Value)
}

//输出：
//good morning
//hello world
//hi lili

注意上面例子的三个输出是按 Key 从小到大排序的，这并非偶然。刚才已经说过 NodeIterator 的遍历是有序的，因此这里的输出也肯定是有序的。

TrieSync

TrieSync 不是 trie 模块的主要功能，应用得也比较少，只在以太坊的 downloader 模块中用来辅助同步代表 State 的 trie 对象。与 TrieSync 有关的有以下几个方法：

func NewTrieSync(root common.Hash, database DatabaseReader, callback TrieSyncLeafCallback) *TrieSync
func (s *TrieSync) AddSubTrie(root common.Hash, depth int, parent common.Hash, callback TrieSyncLeafCallback)
func (s *TrieSync) AddRawEntry(hash common.Hash, depth int, parent common.Hash)
func (s *TrieSync) Missing(max int) []common.Hash
func (s *TrieSync) Process(results []SyncResult) (bool, int, error)
func (s *TrieSync) Commit(dbw DatabaseWriter) (int, error)
func (s *TrieSync) Pending() int

其中NewTrieSync用来生成一个新的 TrieSync 对象并调用 AddSubTrie 方法为同步 root 结点作准备。Peinding 用来获取当前的 Trie 对象有几个结点待同步；而 Missing 则返回待同步结点的哈希。当调用者通过网络获取到这些结点的数据时，它会调用 Process 进行处理。在 Process 内部会解析并记录这些结点，如果解析结果表示它们还有子结点，则加入 missing 和 pending 队列里。当调用者再次调用 Missing 方法时，就会获取到这些缺失的子结点的哈希。这样不断循环，直到 Pending 队列为空，表示所有结点同步完成。整个过程的示意代码如下：

trSync := trie.NewTrieSync(root, db, callback)
for trSync.Pending() != 0 {
missHashs := trSync.Missing(0)

results := downloadTrieNode(missHashs)

trSync.Process(results)
}

trSync.Commit(db)

我们可以看到 TrieSync 并不具备同步的功能，它只是对结点的解析和组装。所以我觉得这个名字起得很有迷惑性，如果是我，我会把它叫做TrieBuilder。

Database

Database是 trie 模块对真正数据库的缓存层，其目的是对缓存的节点进行引用计数，从而实现区块的修剪功能。Database对外提供的方法有：

func NewDatabase(diskdb ethdb.Database) *Database
func NewDatabaseWithCache(diskdb ethdb.Database, cache int)*Database
func (db *Database) DiskDB() DatabaseReader\
func (db *Database) InsertBlob(hash common.Hash, blob []byte)\
func (db *Database) Node(hash common.Hash) ([]byte, error)\
func (db *Database) Nodes() []common.Hash\
func (db *Database) Reference(child common.Hash, parent
common.Hash)\
func (db *Database) Dereference(root common.Hash)\
func (db *Database) Cap(limit common.StorageSize) error\
func (db *Database) Commit(node common.Hash, report bool) error\
func (db *Database) Size() (common.StorageSize, common.StorageSize)

其中NewDatabase或NewDatabaseWithCache用来创建一个Database对象，其参数diskdb是一个数据库接口。

在以太坊早期的 trie 模块中是没有Database对象的，加上这个就是为了增加节点引用计数功能，实现区块的修剪。详细信息我们后面再进行介绍。

目录结构

trie 模块功能的实现代码全部位于以太坊项目的 trie 目录中，且没有子目录。下面我们对主要的源代码文件作简单的说明。

• encoding.go\

  在上篇文章中我们提到过在 Trie 内部 key 的最小单位是 nibble 而不是 byte，以及 key 在从数据库存取的时候是如何编码的。这个文件里的几个函数实现了这两大块功能。（nibble 就是将一个 byte 的高 4 位和低 4 位拆成俩字节得到的值，比如将 0xab 拆成 [0xa
  0xb]，具体请参看trie 上篇）

• hasher.go\

  hasher.go 中的代码实现了从某个结点开始计算子树的哈希的功能。可以说这个文件里的代码实现了以太坊的 Trie 的默克尔树特性。

• node.go\

  在上篇文章中我们介绍过为了缩短无分支路径上的结点数量，以太坊使用了不同的结点类型和结构。这个文件里的代码就是定义了一个 Trie 树中所有结点的类型和解析的代码。

• sync.go\
  sync.go 中的代码实现了前面说的 SyncTrie 对象的定义和所有方法。
• iterator.go\
  iterator.go 中的代码定义了所有枚举相关接口和实现。
• secure\_trie.go\
  secure\_trie.go 中的代码实现了 SecureTrie 对象。

• errors.go\

  errors.go 中只定义了一个结构体：MissingNodeError。当找不到相应的结点时，就会返回这个错误。

• proof.go\

  proof.go 中只包含了 Prove 和 VerifyProof 两个函数，它们只在轻量级以太坊子协议（LES）中被使用。这两个函数被用来提供自己拥有某一对 (key,
  value) 的证明数据，和对数据进行验证。

• trie.go\
  trie.go 实现了 Trie 对象的主要逻辑功能。
• database.go\
  database.go 实现了Database对象的主要逻辑功能。

实现框架

前面我们说过，以太坊的 trie 模块提供了 4 个主要的对象和接口：Trie、SecureTrie、SyncTrie 和 NodeIterator。然而 trie 模块的核心功能是 Trie 对象，所以我们这里仅针对 Trie 作介绍（SecureTrie 与 Trie 是类似的，实际上 SecureTrie 基本上是调用了 Trie 的方法）。

Trie 对象的功能总得来看可以分成两部分：(key,value)的增删改查和 Hash 与 Commit 功能。下面我们分别对其介绍。

Trie 对象的增删改查

Trie 对象的 Get、Update、Delete 等方法实现了其增删改查的功能（当然也包含 TryXXX 等几个类似的方法）。其实 Trie 对象本质上是一棵树，对于树的增删改查操作，也就是对树的某一路径上所有结点的访问。所以在 Get/Delete 等方法的实现代码里，主体结构就是对节点类型的 type
switch，并根据不同的节点类型和目的（新增或删除）对节点进行操作。我对这一过程进行了一下规纳，如下图：

\

从图中可以看出，在 key 的驱动下，我们循环获取当前部分 key 所对应的结点（不断的“查字典”），并根据节点类型的不同使用不同的方式获取下一个结点。具体来说，如果是 shortNode，则其 value 存储的是下一个结点；如果是 fullNode，则 Children 数组中存储的是下一个节点 ------ 你需要根据 key 的值来确定到底是数组中的哪个元素；如果是 hashNode，则说明这个结点还没有被从数据库中加载，只是存了一个结点哈希而已，因此要先载入并解析，再进行处理；如果是 valueNode，则说明找到了 key 对应的 value 值，停止查找。

从以上的流程中也可以看出，要理解 Trie 以太坊中 Trie 的实现，关键要理解这 4 个结点类型以及它们是如何被使用的。在上篇中我们已经详细介绍过 shortNode 和 fullNode 的设计原理，这里我们再结合代码，详细地介绍一下这四个节点以及它们在代码中的用法。

在介绍 4 个结点类型之前，我们必须先说明一下 node 类型。这是一个接口类型，是 4 个结点类型的抽象（上面提到的 type
switch 就是针对这个 node 接口类型进行的）。在 shortNode 和 fullNode 中，使用 node 接口代表其子结点，而不管子结点是什么类型。

fullNode

我们首先来看 fullNode 的定义：

// code in node.go
fullNode struct {
Children [17]node
flags    nodeFlag
}

结构体中 flags 字段记录了一些结点的其它信息，可以忽略不看，我们重点关注 Children 字段。上篇中我们提到过根据数据的元素个数来区分 fullNode 和 shortNode 类型，这里可以看到 Children 字段恰好就是一个 17 个元素的数据（是的，写入数据库时只写入 Children，而不写入 flags 字段）。

相信你现在已经可以很好地理解对 fullNode 的相关操作了。当遇到一个 fullNode 时，我们将 key[pos]作为索引，从 Children 数组中取出下一个结点。这里不得不提一下 key[pos]的值为 16 的情况。上篇中我们提到过两个情况：一是 []byte 类型的 key 在 Trie 内部会被转换成 nibble 数组，并在 nibble 数组最后添加一个值 16 代表 key 已到达结尾（参考 keybytesToHex 函数）; 二是 fullNode 的 17 个元素中最后一个元素代表的是 value 而不是子结点。因此这里如果 key[pos] 的值是 16，则取到的是 Children 数组的最后一个元素，也就是 value。相信到这里，你可以完全理解为什么要在 key 尾部加一个值，以及为什么这个值是 16 而不是 17 或 18 等其它值。

shortNode

shortNode 的定义如下：

//code in node.go
shortNode struct {
Key   []byte
Val   node
flags nodeFlag
}

同样的我们忽略 flags 字段。可以看到 shortNode 有两个元素：Key 和 Val，这与我们之前介绍的一致（17 个元素的是 fullNode，2 个元素的是 shortNode）。

当遇到一个 shortNode 时，首先要对比 key 是否有 shortNode.Key 保存的前缀，如果是则 Val 字段代表了下一个结点，如果不是，则代表树中根本存在 key 这条路径。

shortNode 稍微特殊一点的处理是新加分支。比如一个 shortNode 的 Key 保存的是 "hello"，现在要新增一个 key 为 "held"，那么就要把 shortNode 一分为二，中间插入一个 fullNode。这个过程虽然麻烦一些但不难理解，我们这里就不详细展开了。

hashNode

hashNode 的定义如下：

type hashNode []byte

hashNode 就是一个简单的 byte
slice，它的内容就是某个结点的哈希（所以才叫做 hashNode）。为什么会有这个结点类型呢？

这个类型的存在是由结点从数据库中延迟加载的机制造成的。之前我们说过，Trie 的数据是存储在数据库中的。当我们使用某个 root 哈希创建一个新的 Trie 对象时，不会将所有子结点都一下子加载到内存中，而是用到再去加载。例如当我们创建新的 Trie 对象时，会根据 root 哈希从数据库中加载根结点。假设根结点是一个 fullNode，那我们接下来是否要继续将它的 16 个子结点加载到内存中呢？答案是不需要的，我们只需要让根结点的 Children 数组保存子结点的哈希（其类型当然是 hashNode），在需要时使用这个哈希从数据库中加载，并替换掉原来的哈希。其它结点的处理方法也是这样。这就是 hashNode 的意义。

valueNode

valueNode 的定义如下：

type valueNode []byte

与 hashNode 类似，valueNode 也是一个 byte
slice。它的意义是代表 value 数据，而不再是一个结点了（虽然名字里仍有 node 这个词）。如果在访问结点时遇到这个类型的结点，说明已经找到了 key 所对应的 value。

Trie 的 Hash 与 Commit

Trie 的另一个非常有特色的地方在于，它可以做永久性存储，也可以像默克尔树那样，获取根结点的哈希。这一小节里我们对这两个特性做个简单的介绍。

其实的树类数据结构想要做永久性存储，面临的问题都差不多。我觉得一个最主要的问题是，在数据库中没有了内存指针，如何对子结点进行引用。解决这个问题的方法有多种，比如为每个结点编号且存储时将指针改为编号；或者像以太坊这样使用结点哈希引用结点。这些方法的道理都是类似的。

之所以将这两个功能放在一起讲，也是因为它们内部的实现实际上用的是同一段代码。Trie.Hash 和 Trie.Commit 方法最终都会调用内部方法 Trie.hashRoot（Trie 对象中还有两个方法 Trie.Root 和 Trie.CommitTo，但与 Trie.Hash、Trie.Commit 都是一样的代码）。在 hashRoot 方法中，会调用内部对象 hasher 的 hash 方法。这个方法的就是遍历当前树在内存中每一个结点，将所有 shortNode 和 fullNode 结点变成 hashNode（代码中叫压缩，collapsed）。直接看代码会更容易理解这个过程（下面的代码都是经过简化的，目的是为了更清晰的描述计算 Trie 的 Hash 和写入数据库的方法）

Trie.Hash

func (t *Trie) Hash() common.Hash {
//注意hashRoot的参数为nil，即只计算哈希不保存到数据库中
hash, cached, _ := t.hashRoot(nil)
t.root = cached
return hash
}

Trie.Commit

func (t *Trie) Commit() (root common.Hash, err error) {
hash, cached, err := t.hashRoot(db)
t.root = cached
return hash
}

Trie.hashRoot

func (t *Trie) hashRoot(db DatabaseWriter) (node, node, error) {
h := newHasher()
return h.hash(t.root, db, true)
}

hasher.hash 及相关代码：

//hash返回的第一个node为hashNode，第二个node为传入参数n的缓存（其实也可以理解成拷贝）
//collapsed为“压缩的”结点，即把正常的shortNode或fullNode变成一个hashNode。
func (h *hasher) hash(n node, db DatabaseWriter, force bool) (node, node, error) {
collapsed, cached, err := h.hashChildren(n, db)

hashed, err := h.store(collapsed, db, force)
return hashed, cached, err
}

//hashChildren与hash类似，返回的第一个node为hashNode，第二个node为传入参数original的缓存
func (h *hasher) hashChildren(original node, db DatabaseWriter) (node, node, error) {
switch n := original.(type) {
case *shortNode:
collapsed := n.copy()
collapsed.Key = hexToCompact(n.Key)

cached := n.copy()
cached.Key = common.CopyBytes(n.Key)

if _, ok := n.Val.(valueNode); !ok {
    collapsed.Val, cached.Val, err = h.hash(n.Val, db, false)
}
return collapsed, cached, nil

case *fullNode:
// Hash the full node's children, caching the newly hashed subtrees
collapsed, cached := n.copy(), n.copy()

for i := 0; i < 16; i++ {
    collapsed.Children[i], cached.Children[i], err = h.hash(n.Children[i], db, false)
}
cached.Children[16] = n.Children[16]
return collapsed, cached, nil

default:
// Value and hash nodes don't have children so they're left as were
return n, original, nil
}
}


//h.store计算collapsed结点的哈希；如果db不为nil，则将collapsed结点保存到db中。
//Trie.Hash和Trie.Commit的区别也仅仅体现在这里。将普通结点变为hashNode这一操作也是
//发生在这里
func (h *hasher) store(n node, db DatabaseWriter, force bool) (node, error) {
h.tmp.Reset()
if err := rlp.Encode(h.tmp, n); err != nil {
panic("encode error: " + err.Error())
}

h.sha.Reset()
h.sha.Write(h.tmp.Bytes())
hash = hashNode(h.sha.Sum(nil)) //将普通结点转变成对应的hashNode

if db != nil {
return hash, db.Put(hash, h.tmp.Bytes())
}
return hash, nil
}

注意上面 hasher.hash 和 hasher.hashChildren 的实现。这两个方法通过相互的递归调用，从叶子结点开始逐步地将所有结点变成 hashNode。

其实 hasher.hash 和 hasher.hashChildren 始终维护着两棵树，也就是它们的返回值的前两个 node。第一棵树是“压缩的”(collapsed) 树，这完全是一棵由 hashNode 组成的树，因此根结点的值也就是整棵树的哈希；第二棵树是原始的树，这样可以防止每次调用 Trie.Hash 或 Trie.Commit 后，所有结点都被变成了 hashNode，后续再次调用 Trie.Get 等方法时又得从数据库中重新加载。

Database

前面我们说过，在早期的以太坊 trie 版本中是没有Database对象的，后来加上这个对象就是用来实现区块的修剪功能（关于区块的修剪可以参看 这里）。那么Database是怎么实现的呢？那就是对内存中的 trie 树节点进行引用计数，当引用计数为时，从内存中删除此节点。

在Database结构体中，对 trie 树节点实现引用计数功能的字段是dirties，它的类型是map[common.Hash]*cachedNode。其中cachedNode代表的是一个有引用计数的节点，它的定义如下：

type cachedNode struct {
node node   // node接口
size uint16

parents  uint32                 // 引用当前节点的节点数量
children map[common.Hash]uint16 // 当前节点的子结点的引用计数

flushPrev common.Hash // flush-list列表的字段
flushNext common.Hash
}

在这个结构体中，parents和children实现了引用计数功能。而flushPrev和flushNext将当前节点加入到了 flush-list 链表中。

insert

我们先看看写入节点时会发生什么。当调用 trie 的 Commit 方法时，最终会调用Database.insert方法，且Database.InsertBlob其实也是调用 insert 方法，因此我们从这个方法看起：

func (db *Database) insert(hash common.Hash, blob []byte, node node) {
//已存在立即返回
if _, ok := db.dirties[hash]; ok {
return
}
//构造cacheNode
entry := &cachedNode{
node:      simplifyNode(node),
size:      uint16(len(blob)),
flushPrev: db.newest,
}
//引用子节点，将所有子节点的parents加1
for _, child := range entry.childs() {
if c := db.dirties[child]; c != nil {
c.parents++
}
}
db.dirties[hash] = entry

//加入flush-list链表
if db.oldest == (common.Hash{}) {
db.oldest, db.newest = hash, hash
} else {
db.dirties[db.newest].flushNext, db.newest = hash, hash
}
db.dirtiesSize += common.StorageSize(common.HashLength + entry.size)
}

Database.insert的主要逻辑非常简单，就是构造一个新加入的cacheNode节点，然后增加所有子节点的引用计数（parents 字段）。注意这里并没有增加新节点自身的 parents 计数，因为这里只是往数据库里加入一个新节点，没有证据显示有人引用了这个节点。

reference

以太坊在进行区块的修剪时会调用Database.Reference和Database.Dereference两个方法。为了分析的完整一些，我们先来看看修剪时的调用：

func (bc *BlockChain) writeBlockWithState(block *types.Block, receipts []*types.Receipt, state *state.StateDB) (status WriteStatus, err error) {
......
if bc.cacheConfig.Disabled {
......  
} else {
triedb.Reference(root, common.Hash{}) // metadata reference to keep trie alive
......

for !bc.triegc.Empty() {
......
triedb.Dereference(root.(common.Hash))
}
}
}

这里先引用一整棵树，经过一些判断和处理，再找合适机会解引用这棵树（详细分析请参看 这里 ）。

对节点进行引用的功能主要在Database.reference中实现，我们来看看这个方法：

func (db *Database) reference(child common.Hash, parent common.Hash) {
//如果child节点不在缓存中，立即返回
node, ok := db.dirties[child]
if !ok {
return
}
//如果children字段不存在则构造并继续后面的执行。
//如果children已存在说明已经引用过子节点了，那么如果child变量代表的不是根节点，就直接返回
if db.dirties[parent].children == nil {
db.dirties[parent].children = make(map[common.Hash]uint16)
} else if _, ok = db.dirties[parent].children[child]; ok && parent != (common.Hash{}) {
return
}

//增加引用计数
node.parents++
db.dirties[parent].children[child]++
}

这个方法就是增加child和parent节点的各自的引用计数。但这里有一个特殊的地方，就是如果child已经被parent引用过了，且child代表的不是一个根节点，那么就不继续增加parent对child的引用了；如果child代表一个根节点，还是要继续增加parent对child的引用。

这个处理有些难以理解，我们多解释一下。当父节点已经引用过某个子节点时，不再增加对子节点的引用是合理的，因为一个父节点只能引用
某个特定的子节点
一次，不存在引用多次的情况。但为什么parent为common.Hash{}时，还要继续引用呢？

这是因为在调用Database.Reference时，如果child参数是一个根节点，那么parent的值肯定是common.Hash{}，也即common.Hash{}是任一 trie 树的根节点的父节点；所以这里判断parent是否是common.Hash{}，也就是在判断child参数是否是一个根节点。对根节点的引用与对普通节点引用的不同之处在于，普通节点的引用发生在 trie 树的内部，因此刚才说了，一个父节点只能引用
某个特定的子节点
一次；而根节点是可以被 trie 树以外的地方引用的，比如在 miner 模块中引用了某个 trie 树的根节点，然后 blockchain 模块又对这个根节点引用了一次。所以这种情况不存在common.Hash{}只能引用某个根节点一次的情况。

deference

下面我们再来看看解引用的代码。解引用主要在Database.dereference中实现：

func (db *Database) dereference(child common.Hash, parent common.Hash) {
// Dereference the parent-child
node := db.dirties[parent]

//首先解除父节点对子节点的引用
if node.children != nil && node.children[child] > 0 {
node.children[child]--
if node.children[child] == 0 {
delete(node.children, child)
}
}

//如果child不存在，立即返回
node, ok := db.dirties[child]
if !ok {
return
}

//减小对child参数代表的节点的引用
if node.parents > 0 {
node.parents--
}

//如果没人再引用这个节点，则删除它
if node.parents == 0 {
//将这个节点从flush-list中删除
switch child {
......
}

//解除对所有子节点的引用，然后删除节点
for _, hash := range node.childs() {
db.dereference(hash, child)
}
delete(db.dirties, child)
db.dirtiesSize -= common.StorageSize(common.HashLength + int(node.size))
}
}

这段代码逻辑也比较简单，已经用中文注释进行了说明，这里就不再赘述了。但需要多说一点的时，只有某个节点将要被删除时，才会解引用所有子节点，而不是解引用某个节点的同时也解引用所有子节点。想象一下存在一个引用计数为 2 的节点 A，它有一个引用计数为 1 的节点 B（也即 B 只被 A 引用了）。当我们对 A 进行解引用时，A 的计数变成了 1，如果我们此时同时解引用 A 的子节点，那么 B 的计数将变成 0 从而被删除，但 A 仍然需要这么节点。因此只有当 A 的引用计数变为 0 将要被删除时，才应该解引用它的所有子节点。

flush-list

前面我们多次提到 "flush-list" 这个概念，现在我们就来看看它是什么。要了解 flush-list，首先要了解Database.Cap的功能。这个方法将缓存中的数据刷到真实的数据库中，直到缓存占用的内存量达到参数的要求。flush-list 就是决定在刷新缓存时，先刷哪个节点、最后刷哪个节点的一个双向链表。Database.oldest和Database.newest定义了这个链表的头和尾，链表的元素是cachedNode，而将cacheNode加入到这个链表中的字段就是cacheNode.flushNext和cacheNode.flushPrev。

我们直接看一下Database.Cap是如何使用这个链表的：

func (db *Database) Cap(limit common.StorageSize) error {
......

oldest := db.oldest
for size > limit && oldest != (common.Hash{}) {
// Fetch the oldest referenced node and push into the batch
node := db.dirties[oldest]
if err := batch.Put(oldest[:], node.rlp()); err != nil {
db.lock.RUnlock()
return err
}

......

size -= common.StorageSize(3*common.HashLength + int(node.size))
oldest = node.flushNext
}

......
}

可以看到这是一个典型的链表的遍历。至于其它对 flush-list 插入和删除的代码，相信在了解了它的功能以后，会很容易看懂，因此这里就不再详细说明了。

总结

在这篇文章中，我们结合源代码，介绍了以太坊中 trie 模块的功能与实现。trie 模块的代码组织还是非常工整的，主要文件有 trie.go、node.go、hasher.go、encoding.go 和 iterator.go。

trie 模块的主要对象就是 Trie。想要理解 Trie 的实现原理，关键是弄明白代码中的 4 种 node 类型，以及 key 的编码规则（encoding.go）。

唯一我觉得不太好的是，在 trie.go 及其它源文件中，到处都是关于 node 的 type
switch。我觉得这几乎完全可以放到一个函数中去做，至少可以不像现在这样，在 Get/Upate/Delete 等方法中都有一套 type
switch。