Trie，Trie，Patricia和Merkle Patricia Trie

Question

你能向我解释一下这四种尝试的主要区别吗？

谢谢

Answer 1

trie只是一些信息，比如存储单词狗，然后将其从上到下存储为d-o-g。维基百科的页面显示了这张图片：

正如你所见，它储存了几个词，如"to“、”茶“、"ted”“10”、"A“、"inn”。这些单词中的每一个都是这个数据结构中的关键。因此，我用" to“查询trie数据库，它将返回7，遍历将首先到达t。它节省了搜索数据库中每个单词的时间。把它看作是通过迭代每个字符来创建一个越来越小的组。因此，假设您查询“10”，数据库首先会说，让我们看看以"t“开头的所有单词，然后是"te"，然后是”10“，它只返回一个条目。

三根包括对这一结构的改进。在我前面的狗和点被存储的例子中。它不是将d和o作为节点存储在trie中，而是将"do“存储为节点，将”狗“和”点“存储为该节点的子节点。这意味着遍历较少，但如果大坝出现，它必须创建d-a-m和dam g，因为现在有d-a和d-o的组合，而不仅仅是dam单词。

我相信这幅画是很清楚的。它不是将每个字符存储为trie的一个节点，而是将节点下面所有单词中使用的字符连接到一个节点中。如果你看一下鲁伯，在你动手之前，你可以想象鲁本斯在e节点上只有一个节点。但是由于我们添加了Ruber，所以我们必须创建两个节点。

这就是尝试的基础，现在进入尝试。下面是一幅帮助我们理解如何工作的图片：

这是很复杂的，但它可以帮助您了解这个trie是如何工作的。正如您所看到的，现在有3种不同类型的节点，我们不再仅仅关注泡沫中的"e“或"ear”，而是一些更复杂的信息，但它遵循类似的步骤。顶部有几把钥匙，你可以看到。看看"a711355“，它的值为45.0ETH。现在试着从顶部开始穿越trie。首先，我们有一个扩展节点，它有一个共享的a7，然后下一个节点，它是一个分支节点，它有16种不同的下一次遍历的可能性，所以我们选择1，因为我们遵循我们的键。然后，来自那里的节点有一个键端1355，它完成了trie的遍历，我们现在收到的值为45.0ETH。

正如您可能注意到的，每个节点都有一个字符串的一部分，扩展节点有一个共享的小块，它是我们用于遍历的字符串的一部分，分支节点包含0-f在十六进制中，它将代表字符串中的一个字符，然后叶节点中的键端代表其余的遍历。前缀在构造时帮助trie。

除了遍历之外，这些尝试并没有增加太多内容，它只是针对巨大的数据进行了优化。例如，对于基值trie中的每个单独字符，分支节点的替代方案是2-16个不同的节点。

有关merkle是如何优化基trie的更多技术信息，您可以查看维基。我想我把他们做得很好了。

现在我可以讨论levelDB如何存储这些值，但这超出了问题的范围。Patricia尝试只是基尝试，所以我没有为Patricia尝试包含单独的部分。