B-Tree和Trie搜索速度对比

Comparison of search speed for B-Tree and Trie

我正在尝试找出哪个在搜索速度方面更有效，是 trie 还是 B-Tree。我有一本英文词典，我想在该词典中有效地找到一个词。

如果"more efficient in time of search"你指的是理论时间复杂度，那么B树提供O(logn * |S|)1的搜索时间复杂度，而trie提供O(|S|)时间复杂度，其中|S|为查找字符串的长度，n为字典中的元素个数。

如果"more efficient in time of search"指的是现实生活中的运行时间，那要看实际的实现、实际的数据和实际的搜索行为。一些可能影响答案的例子：

  • 数据大小
  • 存储系统（例如：RAM/Flah/disk/distributed文件系统/...）
  • 搜索分布
  • 每个实现的代码优化
  • （以及更多）

（1）有O(logn)次比较，每次比较需要O(|S|)次，因为需要遍历整个字符串来决定哪个更高（最坏情况分析）。

这取决于您的需要。如果你想获得整个 子树 ，B+Tree 是你的最佳选择，因为它 space 高效，而且 B+ 树的分支因子会影响其性能（中间节点的数量）。如果h是树的高度，那么nmax ~~ bh。因此 h ~~ log(nmax) / log(b).

用 n = 1 000 000 000 和 b = 100，我们有 h ~~ 5。因此，这意味着只有 5 指针取消引用才能从根到叶。它比 Trie 更 cache-friendly。

但是如果你想从子树中得到第一个Nchildren，那么Trie是最好的选择，因为你只需要访问较少的节点比在 B+ 树场景中。 trie.

也很好地处理了单词前缀补全