binary-tree - 比特币默克尔树总是二元的吗？

Question

比特币默克尔树总是二元的吗？

(1) 我想知道 Merkle 树的查找效率。

(2) 我没有发现任何证据表明 Merkle 树是强制二进制的，这将允许 O(log2 n) 查找算法。

(3) 如果一个节点可能有任意数量的子节点，那么查找函数将有一个 O(logK n * K)，其中 K 是允许的最大子节点数（据我所知）。

Answer 1

根据定义，Merkle 树是二元的，请看这里的原始专利。比特币中的树结构也是二进制的。

这些树不像传统的搜索树那样是查找树，而是它们被用作以后摆脱区块链数据的一种方式，但有证据证明给定“根节点”特定数据存在于块中。

无需传输带有n交易的整个比特币区块以显示您的交易存在于特定区块中，您只需提供log(n)来自 merkle 树的节点。