date
Oct 12, 2024
icon
password
Pin
Pin
Hide-in-Web
Hide-in-Web
网址
type
Page
slug
btc-merkle-tree
tags
知识点
category
bottom
bottom
Hide-in-Config
Hide-in-Config
comment
Show
status
Published
summary
Binary tree 指的就是 二叉树。
Merkle 树和二叉树是两种数据结构，尽管它们有相似之处，但它们的用途和结构存在差异。
1. Merkle 树
Merkle 树（也称为哈希树）是一种特殊的树形数据结构，用于高效且安全地验证大量数据的完整性。其每一个叶子节点包含数据的哈希值，而非叶子节点存储其子节点的哈希值，直到根节点（Merkle Root），其值由所有叶子节点通过一系列哈希计算得出。
特点：
- 层次结构：每个节点包含一个哈希值，叶子节点包含数据本身的哈希值，非叶子节点通过将其子节点的哈希值组合后再次进行哈希运算生成。
- 高效验证：Merkle 树允许通过比较部分哈希值快速验证数据是否被篡改，尤其在区块链中，它常用于验证大批量数据的完整性。
- 用途：被广泛应用于区块链技术（如比特币和以太坊），因为它允许只需部分数据即可进行验证，而不必处理整个数据集。
工作原理：
- 从叶子节点开始，每个节点都是其子节点哈希值的组合。例如，如果两个子节点是 A 和 B，那么它们的父节点的哈希值为
H(A + B)。这个过程递归进行，最终生成根节点（Merkle Root）。
- 如果某个数据块被修改，其对应的叶子节点的哈希值会改变，进而影响到父节点，直到根节点。这种结构使得我们只需验证少量节点即可检查整个树的完整性。
2. 二叉树
二叉树（Binary Tree）是一种更通用的树形数据结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。它没有特定的哈希值要求，主要用于结构化存储数据和提供高效的搜索、插入、删除等操作。
特点：
- 层次结构：每个节点最多有两个子节点，构成了一个树形结构。数据从根节点开始按一定顺序排列。
- 应用：二叉树广泛用于数据存储、搜索算法（如二叉搜索树）、表达式解析等场景。
- 没有哈希验证：二叉树与哈希无直接关联，不能像 Merkle 树一样用于数据完整性的验证。
3. Merkle 树与 哈希指针 的关系
Merkle 树与哈希指针密切相关，因为它依赖哈希值来验证数据的完整性。具体来说：
- 哈希指针：Merkle 树的每个节点本质上可以视为一个哈希指针，它不仅指向其子节点，还包含子节点数据的哈希值。这样，当数据发生变化时，哈希值就会改变，从而检测到异常。
- 数据验证：通过哈希指针，Merkle 树可以高效地进行数据完整性验证。当你需要验证某个叶子节点的正确性时，只需递归比较其父节点的哈希值，而无需检查整个树。
4. Merkle tree 与 Binary tree 的结合
区块链中，常将 merkle tree 的树结构设置为 binary tree 的形式，因为 binary tree 具有效率高、计算简单等特点。