二叉树

本文深入对比了以太坊新型状态树结构二叉树（Binary Trie, GD-5）与现有生产环境 MPT 的性能表现。研究发现二叉树在读取操作上比 MPT 慢约 1.7 倍，写入操作慢 2.5 倍，主要原因在于其更深的路径深度导致的 I/O 开销。文章分析了架构差异并提出了未来通过快照层等手段优化性能的方向。

本文探讨了以太坊L1层中二叉树的最新进展，对比了稀疏默克尔树（SMT）和前缀默克尔树（PMT）的优劣，并提出了优化SMT的存储、哈希计算等方面的策略。文章还介绍了状态数据编码方案，以及账户和存储槽的组织方式，同时讨论了哈希函数的选择和树的序列化方法，最后分析了Verkle树的现有进展在二叉树中的可重用性。

本文介绍了二叉Merkle树的结构、算法和安全性。Merkle树通过递归哈希数据块列表来生成唯一的根哈希，用于高效地进行数据一致性验证和成员资格证明。文章详细描述了叶子节点的顺序、层级顺序和规范构建方法，并提供了测试向量。

本文档介绍了二叉 Merkle 树的结构、构造和使用方法，它通过递归哈希数据块列表来生成一个根哈希，用于快速验证数据列表中某个数据的存在性，和数据列表是否相等。文档详细描述了叶子节点的顺序、层级顺序、规范构造算法，以及如何通过比较根哈希来检查两个 Merkle 树的相等性。

EIP-7864 提议对以太坊状态使用二叉树，与 EIP-3102 相比，它提出了一个单一的平衡树，并借鉴了 EIP-6800 的一些思想，例如账户数据、存储槽和代码块的打包。该提议讨论了稀疏树与非稀疏树，以及用于默克尔化的哈希函数的选择，当前草案提议使用非稀疏默克尔树，并在主干级别压缩分支，使用 BLAKE3 哈希函数。