Trie树与B+树的比较

Question

Trie和B+树在对按字典顺序排序的字符串进行索引时有何区别[涉及数十亿个元素]？它们都应该支持范围查询。从性能和实现复杂度角度来看，两者如何比较？

- Fakrudeen

Answer 1

我会说这取决于您所说的"范围(Range)"的含义。

如果您的范围是以"所有以...开头的单词(All words beginning by)"为表达方式，那么我认为使用Trie是正确的选择。另一方面，Trie不适用于像"介于XX和ZZ之间的所有单词(All words between XX and ZZ)"这样的请求。

请注意，B+树(B+ Tree)的分支因子会影响其性能(中间节点的数量)。如果h是树的高度，则n_max ~~ b^h。因此，h ~~ log(n_max) / log(b)。

对于n = 1 000 000 000和b = 100，我们有h ~~ 5。因此，这意味着从根到叶子只需要进行5次指针解引用操作。它比Trie更适合缓存。

最后，B+树(B+ Tree)的实现难度确实比Trie大：它更接近于红黑树(Red-Black Tree)的复杂度。

- Matthieu M.

---

如果你的 Trie 实现得很聪明，那么“在 xx 和 zz 之间的所有单词”并不难。如果你按字典顺序存储边，那么字符串也是按字典顺序排列的。 - Niki Yoshiuchi

然而，利用范围有点困难。在 B+树 中，范围可以由两个指针（开始/结束）定义，并且您可以像在 deque中一样迭代这些指针。在 Trie中，您必须实现迭代（从随机指针到另一个指针），以便能够执行相同的操作，尽管当然不是不可行的，但我担心效率会降低。或者您可以将范围复制到另一个结构中，但那可能代价高昂。 - Matthieu M.

不小心点了踩，本来应该点赞的。现在无法更改了 :( - Suraj Chandran

@Suraj：我编辑了这篇帖子（加了一个空格），所以你应该可以改变你的投票 :) - Matthieu M.

@MatthieuM。我想指出，在将数据结构化为映射到URL、命名空间或类似JSON对象的情况下，拥有与trie相伴的伴生结构的自然性。当你在键中具有明显的分支定界符，例如/或.，并且在对象中使用""、''、{}或[]时，基本上是使用Trie来预解析指针到键映射，以便任何作用域的取消引用都基于所访问的逻辑作用域的深度。对于语义键空间，这非常有用。虽然也有更擅长这种行为的Trie的变体。 - That Realty Programmer Guy

Answer 2

根据您实际的任务：

• 如果您想获取整个子树，则B+树是最好的选择，因为它具有高效的空间利用率。
• 但是，如果您想从子树中获取前 N 个子节点，那么Trie树是最佳选择，因为您只需访问比B+树情况下更少的节点。
• Trie树最常用的任务是单词前缀匹配。

- Denis Bazhenov

---

我使用的一些trie的变体不仅比B树更节省空间，而且对于大多数查询（直接访问、单词完成、范围查询）也更快。 - Mathieu Rodic

Answer 3

维基百科有一些算法复杂性的事实：B+树（特征部分），Trie（不幸的是分散在整篇文章中）。希望这可以帮到你。

- thSoft

---

请在回答中包含相关事实。简单地链接到维基百科并不有用。 - Yakov Galka