之前讲过一篇我对于区块链的理解的文章，文章中讲述的主要数据结构是叫linkedlist的数据结构，但是这么大型的系统，每一个block都使用链表，block与block之间也使用链表进行链接，这无异于将赤壁之战中捆绑所有曹军的战船嘛，显然是不现实的。于是我开始找寻答案，发现原来底层是使用了一个叫merkle tree的数据结构，这玩意在当时读书时候是不曾接触过的，刚好可以学习一下，顺便也记录一下。

从wikipedia的解释，merkle tree实际上是一个hash tree（可以看出区块链也实际上也只是在重复使用哈希的概念而已）。它要解决的问题实际上只有一个，怎么样保证快速的verify某个交易是否已经在链上了，如果是用链表的思路的话，就要遍历链表的每一个节点，按照现在bitcoin主链上的block数量_514166_个，每个block里面拥有的transaction数量是不定的，也就是每一笔交易最坏的情况都要遍历_514166_*_n_次才能找到结果，那这个效率是奇低的。于是，md5这家伙就又进来搞事情了。

借用vitalik大神的一幅图

从图中可以看出，merkle tree实际上就是一个二叉树（以太坊是用非二叉树的形式实现的merkle tree），每一个merkle tree代表一个block，这样一个轻型的客户端需要记录的数据只是一些对应的md5值就可以实现对给定transaction进行校验，从而判断这个交易是否已经在链上，从而防止二次上链。举个栗子：

给定一个交易tx3, 给定hash2和一个merkle md5(md5(tx3)+hash2)的值跟merke root进行比对就可以了，如果相等说明transaction在该里面，否则不在。这个算法实际上也是在用空间换时间的。

在vitalik大神的博客里面，他还详细阐述了binary merkle tree的不足之处，同时也介绍了以太坊为什么需要另外三种树结构，感兴趣的同学可以看看

Reference

• https://blog.ethereum.org/2015/11/15/merkling-in-ethereum/
• https://en.wikipedia.org/wiki/Merkle_tree
• https://medium.com/@evankozliner/merkle-tree-introduction-4c44250e2da7
• https://medium.com/coinmonks/merkle-trees-the-backbone-of-distributed-software-4fa0805132c6