数据结构: 默克尔树 (Merkle Tree)
在开始接触学习区块链的时候，自己最开始接触的数据结构除了链表，最早接触的可能就是默克尔树 (Merkle Tree) 了。
默克尔树，Merkle Tree，本身是种典型的二叉树结构，由一个根节点、一簇中间几点以及最底层的叶子节点组成。相比常规的二叉树，他有着几个主要的特征：
- 最下面的叶子节点存储的就是数据（及其哈希值）
- 非叶子节点（根节点和中间节点）是他子节点的哈希值
还是先上张图来说明，如下图，叶子节点 D0, D1, D2, D3 就是存储的数据，而往上就是逐层的对子节点进行 Hash() 求值。
当然，往复杂延伸点，他也不一定要反映为二叉树，也可以是变种的多叉树，但无论是几个分叉，其父节点都可他的子节点有关联性（通过一定的哈希函数求值）。
也正是这种逐层哈希处理的这种特征，在我们对叶子节点数据那怕稍微稍微变动也会向上逐层反应到父节点，直到根节点。这种特殊性可以用作存在证明，也叫做默克尔证明 (Merkle Proof)，它可以证明你是某个叶子节点的值，如上图，D1 可以证明自己是（从左往右数的）第二个叶子节点的数据，同时又不用把其他叶子节点数据暴露出来。
在比特币 (BitCoin) 区块链中，默克尔树就是这种存在，在每个全节点 (full node) 的每个区块中，都会存储每笔交易的数据，而 BitCoin 会对每笔交易进行哈希，然后按上图进行向上求哈希，最后得到一个根节点，而那串哈希值被称为数字摘要 (digital digest)。
这个摘要会被存储在每个区块的 Header 区，而每个轻节点 (light node) 只需要存储这个摘要就可以验证区块的有效性，而不需要存储整个区块的数据（尤其是大量的交易信息），这样就大大减少了存储空间的需求。
如果我们对叶子节点进行数据排序，碰到不存在的元素数据用空值占位，以此构建一个树，而这结构也被称作稀疏默克尔树 (Sparse Merkle Tree)。这个结构由于排序的特征，它可以证明某个数据是这个树中之一的数据（同时还能定位到在那里），而不需要暴露其他数据，这个结构其实很好，尤其是他能进行数据证明，但同时他也有一个缺点，就是他需要排序，并且可能存在很多空值占位，这样会浪费很多空间。
在以太坊 (Etherium) 区块链中，默克尔树的应用更加广泛，因为以太坊的设计下有三棵树，分别是状态数、交易树和收据树，而他们每个都是一个默克尔树，但他们都按照账户地址进行有序排序，不同于稀疏默克尔树，他们在排序后不会有空值占位，能有效节省空间。同时他还有一个变体的特性，即按前缀进行压缩，来达到更好地节省空间的目的。这个变体地结构被称作 Merkle Patricia Tree，它是默克尔树的一种变种，它的特点是前缀 (Trie) 压缩和有序排序，这样可以有效节省空间，同时还能保证数据的证明。
Reference links: