區塊鏈中的樹

2025年10月10日#BlockChain16

AI 翻譯

這篇文章透過AI由簡體中文翻譯成繁體中文。查看原文

AI 生成的摘要

### 区块链中的树 #### Merkle 树 - **问题**：对一个数组求哈希（n个元素）。 - **传统方案**：将每个数据拼接后哈希，时空复杂度为 $O(n)$。 - **Merkle树**：只需计算路径上的哈希，时空复杂度为 $O(logn)$，但总存储空间增加，仍为 $O(n)$。 #### Trie 树 - 根据前缀进行索引，适用于前缀相似的数据存储。 - 深度最劣为最长字符串的长度，适用于前缀字典查找。 #### Merkle Patricia 树 - 将Merkle树的二叉结构变为16叉。 - 父节点记录16个叉的指针和一个值字段，指针为子节点的哈希值，协助反向查找。 - 同时负责哈希和索引功能，16叉减少深度，从而减少数据库请求次数。 #### Rollup的State Tree - 对map和value进行分离。 #### Verkle Tree - 基于KZG构造16叉树。

Merkle 樹#

問題：對一個數組求哈希（n 個元素）

傳統方案：將每個數據拼接然後哈希，時空複雜度都是 $O (n)$

使用 merkle 樹：只需計算路線上的哈希，時空複雜度都是 $O (logn)$；代價是總存儲空間變大（需要存哈希樹），但是依舊是 $O (n)$

Trie 樹#

根據前綴進行索引，適用於前綴相似的數據存儲

深度最劣為最長字符串的長度（也就是時間複雜度），但不一定是二叉樹

適用於前綴字典的查找

Merkle Patricia 樹#

把 Merkle 樹的二叉變為 16 叉

父節點記錄 16 個叉的指針，再加一個 value 字段表示自己的數值

這裡的指針，就是子節點的哈希值，存在一個key-value DB裡協助反向查找

同時負責哈希和索引兩個功能

16 叉減少深度 -> 減少數據庫的請求次數

Rollup 的 State Tree#

對 map 和 value 進行分離

Verkle Tree#

基於 KZG

依此構造 16 叉樹