Algorithms
比特幣默克爾樹總是二元的嗎？
我一直在對比特幣進行大量研究，試圖在比特和字節級別上理解它。
我想知道 Merkle 樹的查找效率。
我還沒有發現任何證據表明 Merkle 樹是強制二進制的，這將允許
O(log2 n)查找算法。如果一個節點可能有任意數量的子節點，那麼查找函式將有一個
O(logK n * K)，其中K是允許的最大子節點數（據我所知）。
Merkle 樹一般可以有更多的子節點，但比特幣中交易數據的 Merkle 樹是二叉樹。
“默克爾樹是雜湊的二叉樹。” – Bitcoin-Wiki 協議文件
“從這些 txid 中，默克爾樹是通過將每個 txid 與另一個 txid 配對然後將它們散列在一起來建構的。” –開發者指南：交易數據
這樣做的好處是，僅根列表、log 2 (n) 雜湊夥伴和交易索引就足以重建 Merkle 分支，從而允許使用比完整塊少得多的數據進行簡化支付驗證。
如果我沒記錯的話，二進制格式最大限度地減少了完全重建 Merkle 分支所需傳輸的雜湊量，例如 16 個事務
- 二叉樹：root + 4*1 hashpartners + txid + position
- 三子樹：root + 3*2 hashpartners + txid + position
- 四子樹：root + 2*3 hashpartners + txid + position
與希望最小化頻寬使用相比，查找問題可能更小。
是的，我在這裡犯了“以身作則”的謬誤。;)