结构体数组在Ethereum的世界里，数据的最终存储形式是[(6)

假设一个shortNode S已经有一个子节点A，现在要新插入一个子节点B，那么会有两种可能，要么新节点B沿着A的路径继续向下，这样S的子节点会被更新；要么S的Key分裂成两段，前一段分配给S作为新的Key，同时裂变出一个新的fullNode作为S的子节点，以同时容纳B，以及需要更新的A。

如果一个fullNode原本只有两个子节点，现在要删除其中一个子节点，那么这个fullNode就会退化为shortNode，同时保留的子节点如果是shortNode，还可以跟它再合并。

如果一个shortNode的子节点是叶子节点同时又被删除了，那么这个shortNode就会退化成一个valueNode，成为一个叶子节点。

诸如此类的情形还有很多，提前设想过这些案例，才能正确实现MPT的插入/删除/查找等操作。当然，所有查找树(search tree)结构的操作，免不了用到递归。

特殊的那个 - hashNode

hashNode 跟valueNode一样，也是字符数组[]byte的一个别名，同样存放32byte的哈希值，也没有子节点。不同的是，hashNode是fullNode或者shortNode对象的RLP哈希值，所以它跟valueNode在使用上有着莫大的不同。

在MPT中，hashNode几乎不会单独存在(有时遍历遇到一个hashNode往往因为原本的node被折叠了)，而是以nodeFlag结构体的成员(nodeFlag.hash)的形式，被fullNode和shortNode间接持有。一旦fullNode或shortNode的成员变量(包括子结构)发生任何变化，它们的hashNode就一定需要更新。所以在trie.Trie结构体的insert()，delete()等函数实现中，可以看到除了新创建的fullNode、shortNode，那些子结构有所改变的fullNode、shortNode的nodeFlag成员也会被重设，hashNode会被清空。在下次trie.Hash()调用时，整个MPT自底向上的遍历过程中，所有清空的hashNode会被重新赋值。这样trie.Hash()结束后，我们可以得到一个根节点root的hashNode，它就是此时此刻这个MPT结构的哈希值。上文中提到的，Block的成员变量Root、TxHash、ReceiptHash的生成，正是源出于此。

函数实现

代码方面，创建新nodeFlag对象的函数叫newFlags()。在nodeFlag初始化过程中，bool成员dirty置为true，表明了所代表的父节点有改动需要提交，同时hashNode成员hash，直接设空。

//trie/trie.go

func(t*Trie)newFlag()nodeFlag{

returnnodeFlag{dirty:true,gen:t.cacheGen}

}

每个hashNode被赋值的过程，就是它所代表的fullNode或shortNode被折叠(collapse)的过程。基于效率和数据安全考虑，trie.Trie仅提供整个MPT结构的折叠操作Hash()函数，它默认从顶点root开始遍历。

func(t*Trie)Hash()common.Hash{

hash,cached,_:=t.hashRoot(db:nil)

t.root=hash

return…

}

func(t*Trie)hashRoot(dbDatabaseWriter)(node,node,error){

if(t.root==nil){…}

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-69032-6.html