B树和Trie搜索速度的比较 [英] Comparison of search speed for B-Tree and Trie

问题描述

我试图找出在搜索速度方面，无论是trie还是B-Tree，效率更高。我有一本英语单词词典，我想高效地在该词典中找到一个单词。

I am trying to find out which will be more efficient in terms of speed of search, whether trie or B-Tree. I have a dictionary of English words and I want to locate a word in that dictionary efficiently.

推荐答案

如果通过在搜索时间上更有效来指代理论时间复杂度，则B树会提供 O（logn * | S |） ¹ 搜索的时间复杂度，而trie提供 O（| S |）时间复杂度，其中 | S | 是所搜索字符串的长度，而 n 是

If by "more efficient in time of search" you refer to theoretical time complexity, then B Tree offers O(logn * |S|)¹ time complexity for search, while a trie offers O(|S|) time complexity, where |S| is the length of the searched string, and n is the number of elements in dictionary.

如果通过在搜索时更有效，您指的是实际的实际运行时间，这取决于实际的实现，实际的数据和实际的搜索行为。可能会影响答案的一些示例：

If by "more efficient in time of search" you refer to actual real life run time, that depends on the actual implementation, actual data and actual search behavior. Some examples that might influence the answer:

• 数据大小


• 存储系统（例如： RAM / Flah / disk /分布式文件系统/...)


• 搜索分布


• 每个实现的代码优化


• （还有更多）

• Size of data
• Storage system (for example: RAM/Flah/disk/distributed filesystem/...)
• Distribution of searches
• Code optimizations of each implementation
• (and much more)

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

(1) There are O(logn) comparisons, and each comparison takes O(|S|) times, since you need to traverse the entire string to decide which is higher (worst case analysis).

这篇关于B树和Trie搜索速度的比较的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！