以太坊中的mpt

1. mpt树实现概述

概述：MPT树是一种基于trie的数据结构，用于高效地存储和处理增量的key-value对，特别适用于需要频繁增删改操作的场景。它通过递归实现所有操作，并支持两种主要操作：根据变动生成新树并持久化更改，以及从节点构造整棵树以同步数据。

数据结构设计中，shortnode和fullnode分别存储值和16个可能的子节点，其中shortnode实现了路径压缩。valuenode直接存储值，而hashnode作为节点间引用，嵌套在节点中。节点通过计算nodehash确保唯一性，并使用RLP编码存储，以减少节点数。

基本操作包括创建树、读写删除和提交。创建时，根据给定的hash定位树并可能从数据库加载根节点。读写删除通过递归处理节点，更新后节点标记为已修改，产生新根节点。Commit操作分为两步：计算新hash并提交更改，确保新旧节点的唯一标识。

高级操作如同步和裁剪，MPT树在以太坊中应用时，为了提高效率和避免数据库缓存失效，会采用特殊策略，如快速同步和快照恢复。但裁剪节点时，由于MPT树的特性，依赖离线处理而非实时引用计数。