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

区块链的操作

从逻辑上讲，既然BlockChain和HeaderChain都管理着一个类似单向链表的结构，那么它们提供的操作方法肯定包括插入，删除，和查找。

查找比较简单，以BlockChain为例，它有一个成员currentBlock，指向当前最新的Block，而HeaderChain也有一个类似的成员currentHeader。除此之外，底层里还分别存有当前最新Block和Header的canonical hash：

这里“LastFast”所存储的是在一种特别的同步方式FastSync下，最新Block的canonical hash。FastSync相比于FullSync，可以仅仅同步Header而不考虑Body，故此得名Fast。

以BlockChain为例，通过”LastBlock”为key从中获取最新的Block之后，用num逐一遍历，得到目标Block的num后，用’h’+num+’n’作key，就可以从中获取目标canonical hash。

插入和删除。区块链跟普通单向链表有一点非常明显的不同，在于Header的前向指针ParentHash是不能修改的，即当前区块的父区块是不能修改的。所以在插入的实现中，当决定写入一个新的Header进底层时，从这个Header开始回溯，要保证它的parent，以及parent的parent等等，都已经写入了。只有这样，才能确保从创世块(num为0)起始，直到当前新写入的区块，整个链式结构是完整的，没有中断或分叉。删除的情形也类似，要从num最大的区块开始，逐步回溯。在BlockChain的操作里，删除一般是伴随着插入出现的，即当需要插入新区块时，才可能有旧的区块需要被删除，这种情形在代码里被称为reorg。

3. 精巧的Merkle-PatriciaTrie

Ethereum 使用的Merkle-PatriciaTrie(MPT)结构，源自于Trie结构，又分别继承了PatriciaTrie和MerkleTree的优点，并基于内部数据的特性，设计了全新的节点体系和插入/载入机制。

Trie，又称为字典树或者前缀树(prefix tree)，属于查找树的一种。它与平衡二叉树的主要不同点包括：每个节点数据所携带的key不会存储在Trie的节点中，而是通过该节点在整个树形结构里位置来体现；同一个父节点的子节点，共享该父节点的key作为它们各自key的前缀，因此根节点key为空；待存储的数据只存于叶子节点中，非叶子节点帮助形成叶子节点key的前缀。下图来自wiki-Trie，展示了一个简单的Trie结构。

PatriciaTrie，又被称为RadixTree或紧凑前缀树(compact prefix tree)，是一种空间使用率经过优化的Trie。与Trie不同的是，PatriciaTrie里如果存在一个父节点只有一个子节点，那么这个父节点将与其子节点合并。这样可以缩短Trie中不必要的深度，大大加快搜索节点速度。

MerkleTree，也叫哈希树(hash tree)，是密码学的一个概念，注意理论上它不一定是Trie。在哈希树中，叶子节点的标签是它所关联数据块的哈希值，而非叶子节点的标签是它的所有子节点的标签拼接而成字符串的哈希值。哈希树的优势在于，它能够对大量的数据内容迅速作出高效且安全的验证。假设一个hash tree中有n个叶子节点，如果想要验证其中一个叶子节点是否正确-即该节点数据属于源数据集合并且数据本身完整，所需哈希计算的时间复杂度是是O（log(n)），相比之下hash list大约需要时间复杂度O(n)的哈希计算，hash tree的表现无疑是优秀的。

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