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叉树