ELI5一棵梅克-帕特里夏树是如何工作的？

Question

我知道Merkle树是散列的散列，它们的优点是您只能验证一个子树。那帕特丽夏呢？三分是什么意思？它在以太里是怎么用的？

Answer 1

Trie (也称为数字树，前缀trie或基trie)

一种有序的树数据结构，用于存储动态集合或关联数组，其中键通常是字符串。节点在树中的位置定义了与其关联的键。https://en.wikipedia.org/wiki/Trie

钥匙"A“、"to”、“茶”、"ted“、”10“、"i”、"in“和"inn”。

Patricia -检索字母数字编码信息的实用算法(来源)(唐纳德·R·莫里森(唐纳德·莫里森)的组织论文)。Patricia是遍历trie时在每个节点上的一个二元基trie二进制选择；这是在Ethereum中修改的。

来源：https://en.wikipedia.org/wiki/File:An_示例_的_多么_至_发现_一个_字符串_在……里面_一个_帕特里夏_trie.png

在ethereum中，使用十六进制-X字符，从一个16个字符“字母表”。因此，trie中的节点有16个子节点(16个字符十六进制“字母表”)和最大深度X。注意，十六进制字符被称为“啃”。

Merkle Trie

正如所描述的这里，默克尔一词意味着

根节点成为整个数据结构的加密指纹。

Ethereum改进的Merkle

黄纸描述了一种改进型的merkle。这定义了三种不同的节点类型:扩展、分支和叶子。下面的图表使用简化的世界状态对它们进行了分解：

Answer 2

“‘Trie”来源于单词检索，因为它只使用一个单词的前缀来在字典中找到它。它是一个有序的树，键通常是以终端符号结尾的字符串，每个顶点代表一个前缀。trie的根通常是一个空字符串，从wikipedia的图表中可以看到这一点。

有关trie和基(Patricia)树之间差异的更多信息。

https://stackoverflow.com/questions/14708134/what-is-the-difference-between-trie-and-radix-trie-data-structures

Ethereum使用的Merkle树的更多规范可以在ethereum博客上找到。

https://blog.ethereum.org/2015/11/15/merkling-in-ethereum/