区块链与Git内部数据结构都以树形数据对象表示——即以默克尔树（Merkle Tree）作为底层数据结构。& x* k/ }8 o, L; [
默克尔树这种现代数据结构是由计算机科学家Ralph Merkle（他也是公钥加密算法共同设计者）在1979年提出（作为对比，Knuth的TAOCP三卷第一版写完是1973年），并以他的名字命名。
8 {6 k/ f6 \8 \  F6 Z  l6 r) q! Z
4 X+ ?+ A3 z! B0 `) n: _这种数据结构的特点是：0 j$ w  L  _. M9 x
大多数为二叉树，也可以多叉树，无论是几叉树，它都具有树结构的所有特点
/ p' h9 {' _% p3 \叶子节点value是数据集合的单元数据或者单元数据Hash" P8 k: H7 _" Z( j9 I. h
非叶子节点的value是根据它下面所有的叶子节点值，然后按照Hash算法计算而得出
6 }& g8 ?6 A; m, K9 I! V5 ^) n! a
5 Q0 L; j& o) l" J; X; d近年来，除了Bitcoin、Ethereum、IPFS，一大批计算机工程突破，都得益于这种数据结构进行完整性校验，例如文件系统ZFS、Btrfs，另一种分布式版本控制系统Mercurial，NoSQL数据库Apache Cassandra、Riak、Dynamo等。BT下载，也是通过默克尔树进行完整性校验。
3 M( h0 \) I3 C' i* o2 f& D要实现完整性校验，最简单的方法是对整个数据文件做Hash运算，把得到的Hash值公布在网上，下载数据后，再次运算Hash值，如果运算结果相等，就表示没有任何的损坏。
' H4 h5 j. {3 g) P+ Z假如从稳定的服务器上下载，那么采用单个Hash来进行校验的形式是可以接受的。但在点对点网络中作数据传输时，会从同时从多个机器上下载，且线路充斥着不稳定，这时需要有更加巧妙的做法。$ q$ F) z2 b0 H. |  H2 U
实际中，都是把比较大的一个文件，切成小块。如果有一个小块数据在传输过程中损坏，只要重新下载这一个数据块就行。当然这就要求每个数据块都拥有自己的Hash值。
( O) D$ d* m' V9 l以我们熟悉的BT下载为例，下载真正的数据之前，会先下载一个Hash列表的。这时有一个问题出现——那么多的Hash，怎么保证它们本身都是正确地呢？( n' y! Y% P$ i" E" v. t
答案是需要一个“根Hash”。把每个小块的Hash值拼到一起，然后对整个这个长长的字符串再做一次Hash运算，最终的结果就是Hash列表的根Hash。于是，如果我们能够保证从一个绝对可信的网站，或者从我们的朋友手里拿到一个正确的根Hash，就可以用它来校验Hash列表中的每一个Hash都是正确的，进而可以保证下载的每一个数据块的正确性了。1 b$ `9 i+ T3 {8 H$ B+ @& q3 X3 X4 \
这种设想挺好，但实际应用中，还有不足，这就是为什么要发默克尔树。( v* l  ]( |2 c
在最底层，与Hash列表一样，数据被分成小块，有相应的Hash和其对应。但是往上走，并不是直接去运算根Hash，而是把相邻的两个Hash合并成一个字符串，然后运算这个字符串的Hash，这样每两个Hash就结婚生子，得到了一个“子Hash”。
( s  _4 k% F; t. |9 ]8 i  y' f如果最底层的Hash总数是单数，那到最后必然出现一个单身Hash，这种情况就直接对它进行Hash运算，所以也能得到它的子Hash。于是往上推，依然是一样的方式，可以得到数目更少的新一级Hash，最终必然形成一棵倒挂的树，到了树根的这个位置，这一代就剩下一个根Hash了，称为默克尔根。
. J' _/ |6 ~. p7 a相对于Hash List，Merkle Tree 的明显的一个好处是可以单独拿出一个分支来（作为一个小树）对部分数据进行校验，这个很多使用场合就带来了Hash列表所不能比拟的方便和高效。