# 默克尔树

By [abyssssssea](https://paragraph.com/@abyssssssea) · 2022-11-12

---

_第一篇文章，写点基础知识吧_

默克尔树又称哈希树，一种树形结构，被广泛应用于密码学相关领域。

特点：

*   叶子节点除了包含数据之外，还包含自身的哈希
    
*   根节点和中间节点的哈希是通过他们的孩子计算而来
    

数据结构：

    struct Node {
      uint val;
      string hash;
      Node[] children;
    }
    

可以利用这个特点，来快速验证一组数据的正确性。

下面列几个常见的应用。

![图取自wiki](https://storage.googleapis.com/papyrus_images/7e75b5dcf832408b1fa6031a69a299520475a9d66a81557021cbec3e678449bf.png)

图取自wiki

### 1\. 快速验证数据是否正确

把数据都存储在最下层的叶子节点，即 L1 ~ L4， 因为根节点和中间节点的哈希都是根据叶子节点计算而来，所以只比较根节点，就能快速判断数据的正确性。

### 2\. 快速定位有问题的数据

在根节点不一致时，我们逐级往下查找子节点不一致的地方，能以 O(lgN) 的时间找到出问题的节点。

---

*Originally published on [abyssssssea](https://paragraph.com/@abyssssssea/daBnvtnIiEbkjFpvTA9V)*