binary-tree - 比特币默克尔树总是二元的吗?
问题描述
比特币默克尔树总是二元的吗?
(1) 我想知道 Merkle 树的查找效率。
(2) 我没有发现任何证据表明 Merkle 树是强制二进制的,这将允许 O(log2 n) 查找算法。
(3) 如果一个节点可能有任意数量的子节点,那么查找函数将有一个 O(logK n * K),其中 K 是允许的最大子节点数(据我所知)。
解决方案
根据定义,Merkle 树是二元的,请看这里的原始专利。比特币中的树结构也是二进制的。
这些树不像传统的搜索树那样是查找树,而是它们被用作以后摆脱区块链数据的一种方式,但有证据证明给定“根节点”特定数据存在于块中。
无需传输带有n
交易的整个比特币区块以显示您的交易存在于特定区块中,您只需提供log(n)
来自 merkle 树的节点。
推荐阅读
- opencv - 如何检测自定义复杂对象?
- java - 单击java按钮时如何执行C++代码?
- apache-kafka - 如何避免依赖加载火花流和卡夫卡?
- javascript - 提到的用户的 addRole 不起作用
- php - 如何使用 laradock 使用 postgres 配置 laravel?无法连接到服务器:端口 5432 上的连接被拒绝
- ios - 快速调用 dequeueReusableCell(withIdentifier:for:) 时内存泄漏
- python - 使用带有 ffmpeg 的每 N 个编号的绘图图像 (.png) 制作视频 (.mp4)
- r - 检查列表对象是否存在并给它们命名
- azure-devops - 在自定义任务中访问 Azure DevOps 其他部分的身份验证
- c++ - UDP 客户端仅在特定情况下卡在 recvfrom