本篇文章分析的源码地址为：https://github.com/ethereum/go-ethereum
分支：master
commit id: 257bfff316e4efb8952fbeb67c91f86af579cb0a
引言
在上篇文章中，我们讲解了以太坊中Trie的主要原理。在这篇文章里，我们通过探索源代码来进一步了解以太坊trie模块。
以太坊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为「压缩的」树，即它的所有子孙结点都是 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 以给定的结点为根，将这个子树「压缩」。
//所谓「压缩」，就是将所有子孙结点变成 hashNode 类型（并将原始节点存储到数据库中）。
//hashChildren 的第一个返回值正是「压缩」树的根；第二个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 始终维护着两棵树，它的前两个返回值分别为这两棵树的根。第一棵树的所有结点都是 hashNode 类型，包括根结点，因此使用这棵树可以很快的获得整棵树的哈希；第二棵树是原始的树，其结点可能是 fullNode 或 shortNode（当然也可能是其它类型）。使用这棵树可以防止每次调用 Trie.Hash 或 Trie.Commit 后，所有结点都被变成了 hashNode，后续再次调用 Trie.Get 等方法时又得从数据库中重新加载。
hasher.hashChildren 用来将某个结点的所有子结点变成 hashNode 类型。作为 hasher.hash 的辅助方法，hasher.hashChildren 也维护了两棵树，不同的是它的第一棵树的根（也就是第一个返回值）并不是 hashNode 类型，只是这个根的所有子孙结点是 hashNode 类型而已。
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。
以上我是对以太坊的trie模块的分析，如有不对的地方还望不吝指正。