数据结构

在区块链中，区块链是块间通过hash指针相连接的链表结构。而在区块中交易数据保存成为梅克尔树的数据结构。

hash 指针

普通指针存储某一个结构体在内存中的地址，

data_structure_001.png

图中指针指向结构体在内存中起始位置地址。

data_structure_002.png

我们都知道一个一个区块连接在一起就形成区块链，这样结构很像链表，但是又不同于链表。不同之处就是区块链使用hash指针指向前一个区块。

这样做好处，我们知道记住区块链最后一个hash值，只要前面有任何改动都会反映到当前hash 值，因为每一个区块的 hash 都包含 block 的内容。我们对比一下普通链表，普通链表我们可以任意修改某一个节点。而区块链是牵一发而动全身。

data_structure_003.png

这样好处我们无需在本地保存区块链中所有的区块，而只保存最近的区块即可，需要时可以从其他节点处进行搜集。但是如何放置恶意节点提供伪造区块呢?

data_structure_005.png

梅克尔树(Merkle Tree)

Merkle Tree 与普通二叉树区别就是用 hash 指针代替了普通指针。

我们对交易数据进行取 hash，然后两两 hash 进行拼接取 hash 值
最顶层是 Merkle Root(梅克尔根)
梅克尔树(Merkle Tree) 类似区块链结构，也是牵一发而动全身，但是二叉树是一种快速的查询结构。也就是保证交易数据不会被篡改。

Merkle Proof

区块头和区块体

区块分为两个部分，区块头和区块体。区块头中保存区块的信息，而区块体包含交易信息。

轻节点和全节点

根据节点保存区块信息大小分为轻节点和全节点。轻节点例如在移动端应用上仅包含区块。那么如何在轻节点上判断一笔交易是否存在。具体方法在我们介绍完 Merkle Proof 大家就理解了。

首先轻节点向对应全节点发起请求
全节点根据请求将路径上hash返回轻节点

data_structure_006.png

如图我们如何在轻节点中判断某一个交易(粉色表示)是否包含在该区块中，轻节点向全节点发起请求，只要全节点把图中标记为蓝色这些 hash 值发送给轻节点就可以了。有了这些 hash 值之后。轻节点在本地计算出标记为绿色 hash 值，用全节点提供蓝色 hash 值一起计算出根 hash 值。这样就可以验证这笔交易是否写入到这个区块。这个过程的时间复杂度是 $O(log(n)$ 。那么如果我们想要证明某一笔交易不再当前区块中，就需要全节点的梅克尔树进行遍历后一一对比每一笔交易来进行判断该笔交易是否存在该区块，这样做时间复杂度是 $O(n)$ ，但是如果我们对交易的hash 值进行排序这样问题的解就变得简单了。