我试图找出在搜索速度方面哪个更有效，无论是trie还是B-Tree。我有一本英语单词词典，我想有效地在该词典中找到一个单词。
如果"在搜索时间更有效"是指理论时间复杂度，那么 B Tree 为搜索提供 O(logn * |S|) 1 个时间复杂度，而 trie 提供O(|S|)时间复杂度，其中|S|是搜索字符串的长度，n是字典中的元素数。
如果"搜索时间更有效"是指实际的实际运行时间，这取决于实际实现、实际数据和实际搜索行为。一些可能影响答案的示例：
- 数据大小
- 存储系统(例如：RAM/Flah/disk/distributed filesystem/...(
- 搜索分布
- 每个实现的代码优化
- (以及更多(
(1(有O(logn)比较，每次比较需要O(|S|)次，因为您需要遍历整个字符串才能确定哪个更高(最坏情况分析(。
这取决于您的需求。如果要获取整个子树，B+Tree是最佳选择，因为它节省空间，并且 B+ 树的分支因子也会影响其性能(中间节点的数量(。如果 h 是树的高度，则nmax ~~ bh .因此 h ~~ log(nmax(/log(b(。
000 且 b = 100 时，我们有 h ~~ 5。因此，这意味着只有 5 个指针取消引用从根到叶。它比Trie更易于缓存。
但是，如果要从子树中获取前N子节点，则Trie是最佳选择，因为与B+树方案中相比，您只需访问更少的节点。此外，单词前缀补全由trie很好地处理。