作为高级攻城狮一定要心中有树，因为这个的确能提升底层认知。
希望每人都能够做到心中有树，面对面试高频问题，方能有的放矢。
01.区块链中的树
体会一下：区块链上交易的篡改，会给区块带来什么影响？
如图是区块链中的一个区块，里面存放了一批已经完成的交易信息，为了方便处理，区块的交易信息组织成Merkle树的形式，区块的块头存储了前一区块的哈希值。
假设叶子节点上的交易3发生篡改，那么交易3对应的哈希值就会变动，变动就会逐级向上传递，直到相应的父节点，最终导致区块的的根哈希发生变化，进而会导致整个区块的哈希发生变化。
一句话：交易的篡改，导致整个区块的哈希变化。
由于交易3的篡改，导致交易3对应的整个区块的哈希发生变动，进而会引起下一个区块上记录的上一个区块的哈希就对不上了，那么是不是要考虑篡改后面的区块呀？但是区块后面的后面的区块也要篡改，子子孙孙无穷匮也。
一句话：交易的篡改，牵一发要动全身，需要篡改整个链条才可以生效，难度可想而知（区块链不可篡改的特性）。
感受一下：如何验证区块上的交易是否存在？
假如需要验证区块上是否真实存在交易3，该怎么去验证？其实我们只需要“哈希2”和“哈希01”就可以证明啦，验证步骤如下。
Step1：获取交易3的哈希值，哈希3=Hash(交易3)；Step2：通过哈希2和哈希3，得到父节点的哈希值：哈希23=Hash(哈希2+哈希3)；Step3：通过哈希01和哈希23的哈希值，得到根节点的哈希值：Root=Hash(哈希01+哈希23)；Step4：将上一步得到的根哈希值Root与区块头中默克尔根哈希值对比，如果相同，则证明该区块中存在交易3，否则说明不存在。
一句话：通过引入默克尔树，比特币采用少量计算及比较，就可以完成交易的验证。
思考一下：如何回收磁盘空间？
随着时间的推移，链越来越长，区块链的数据也逐日增长，数据量级越来越大，对存储肯定要求也越来越高。其实一旦最新交易已经被足够多的区块覆盖，这之前的支付交易就可以被丢弃，以便节省磁盘空间。
如上图所示，交易被哈希进默克尔树，只有根节点被纳入到区块的哈希值。那么老的区块可通过剪除树枝的方式被压缩，树枝内部的哈希不需要被保存，进而可以节省磁盘空间而又不破坏区块的哈希值（堪称设计完美）。
其实比特币的以上种种设计，背后都离不开默克尔树，那默克尔树到底是什么呢？
02.掌握默克尔树
学习任何一门技术，都不要忘记谷哥和度娘，在谷歌输入“MerkleTree”搜之，映入眼帘的就是维基百科的解释。
哈希树（hashtree；Merkletree），在密码学及计算机科学中是一种树形数据结构，每个叶节点均以数据块的哈希作为标签，而除了叶节点以外的节点则以其子节点标签的加密哈希作为标签。哈希树能够高效、安全地验证大型数据结构的内容，是哈希链的推广形式。哈希树的概念由瑞夫·墨克于年申请专利，故亦称墨克树（Merkletree）。
通过搜索我们明白两点。
1.原来MerkleTree也叫做HashTree（哈希树），因为MerkleTree每个叶节点均以数据块的哈希作为标签，而除了叶节点以外的节点则以其子节点标签的加密哈希作为标签，所以又叫做哈希树；2.MerkleTree在维基百科被翻译为墨克树，而在中本聪的论文中又被翻译成了默克尔树。其实到这一步，名字叫什么已经无所啦。
通过这个图我们明白两点。
1.哈希树的顶部为顶部哈希（tophash），亦称根哈希（roothash）或主哈希（masterhash）；2.Hash0-0和Hash0-1分别是数据块L1和L2的哈希值，Hash0是将Hash0-0和Hash0-1连接后所取得的哈希值。
主要应用场景。
1.Merkle树典型的应用场景是点对点网络下载。先从朋友或者网站分享等方式获取可信的Merkle树的顶部哈希；拿到顶部哈希后，就可以通过P2P网络中的非受信来源下载整棵Merkle树；下载得到Merkle树后，就可以根据可信的顶部哈希对其进行校验，验证数据是否完整、是否遭受破坏；2.Merkle树可以被用来快速比较大量的数据，因为当两个Merkle树根相同时，则意味着所代表的数据必然相同；3.开篇中谈到的区块链场景。
03.闲言碎语
默克尔树就分享到这儿，希望大家对默克尔树有个初步认识吧。
文中图片，大都来自于比特币的创始人中本聪的论文，中本聪的论文建议有时间读一读，毕竟是颠覆之作。
区块链2.0的代表技术以太坊Ethereum（不是比特币的一个克隆，而是完完全全独立的一种设计和实现）建议有时间也了解了解。
比特币：