以太坊中的mpt

1. mpt樹實現概述

概述：MPT樹是一種基於trie的數據結構，用於高效地存儲和處理增量的key-value對，特別適用於需要頻繁增刪改操作的場景。它通過遞歸實現所有操作，並支持兩種主要操作：根據變動生成新樹並持久化更改，以及從節點構造整棵樹以同步數據。

數據結構設計中，shortnode和fullnode分別存儲值和16個可能的子節點，其中shortnode實現了路徑壓縮。valuenode直接存儲值，而hashnode作為節點間引用，嵌套在節點中。節點通過計算nodehash確保唯一性，並使用RLP編碼存儲，以減少節點數。

基本操作包括創建樹、讀寫刪除和提交。創建時，根據給定的hash定位樹並可能從資料庫載入根節點。讀寫刪除通過遞歸處理節點，更新後節點標記為已修改，產生新根節點。Commit操作分為兩步：計算新hash並提交更改，確保新舊節點的唯一標識。

高級操作如同步和裁剪，MPT樹在以太坊中應用時，為了提高效率和避免資料庫緩存失效，會採用特殊策略，如快速同步和快照恢復。但裁剪節點時，由於MPT樹的特性，依賴離線處理而非實時引用計數。