在区块链技术的世界里，以太坊以其智能合约功能和图灵完备性闻名，而支撑其安全、高效运转的底层架构中，有三种核心数据结构被称为“树”——它们分别是Merkle Patricia树（MPT）、Merkle树和状态树，这三种“树”并非自然界的植物，而是计算机科学中精心设计的算法结构，共同构成了以太坊数据存储、状态验证和共识机制的核心骨架。

Merkle Patricia树（MPT）：状态数据的“导航仪”

如果说以太坊的全状态是一个庞大的“数据库”，那么Merkle Patricia树（简称MPT）就是这个数据库的“索引系统”，它是一种结合了Merkle树和Patricia Trie（前缀树）优化的数据结构，主要用于存储以太坊的全局状态——即所有账户（账户地址、余额、 nonce、代码存储）和合约存储（合约变量的键值对）的数据。

MPT的核心作用：高效查找与数据验证

MPT的设计解决了两个关键问题：高效的数据检索和轻量级的状态验证。

  • 高效检索：与传统的哈希表不同，MPT通过“路径压缩”技术，将相同前缀的键值对共享同一分支节点，大幅减少了树的深度和节点数量，多个以“0x123”开头的账户地址，会沿着“1→2→3”的路径共享父节点，查询时只需遍历公共前缀，无需遍历整个树。
  • 轻量级验证：MPT的每个节点都会计算唯一的哈希值，根节点的哈希（称为“状态根”）会被打包到区块头中，当需要验证某个账户或合约存储是否存在时，只需提供从目标节点到根节点的“证明路径”（包含路径上的节点哈希），验证者通过计算路径上的哈希值，即可快速确认数据是否属于当前状态,而无需下载整个状态数据库。

MPT的结构：节点类型决定路径

MPT包含四种节点类型，每种节点的结构决定了其在树中的“角色”：

  • 空节点（Null Node）：表示空值，用于简化树的结构。
  • 分支节点（Branch Node）：有17个子节点（0-15对应16种可能的字节值，16表示子节点），用于处理路径分歧，相当于“多岔路口”。
  • 扩展节点（Extension Node）：存储“公共前缀+子节点哈希”，用于压缩路径，减少冗余（例如将“路径0x12→子节点A”压缩为“前缀0x12→哈希值A”）。
  • 叶子节点（Leaf Node）：存储实际的键值对数据（如账户余额、合约变量值），相当于“目的地”。

通过这些节点的组合，MPT能够以O(log n)的时间复杂度完成数据的插入、删除和查询,成为以太坊状态管理的核心引擎。

交易树与收据树：Merkle树的“兄弟搭档”

除了存储全局状态的MPT，以太坊的每个区块中还包含另外两种关键的Merkle树：交易树（Transactions Tree）配图