c - 搜索文件并返回值 - 超快

Question

我有一组数据，其中包含名称、一些子值和关联数值。例如:

James Value1 Value2 "1.232323/1.232334"
Jim   Value1 Value2 "1.245454/1.232999"
Dave  Value1 Value2 "1.267623/1.277777"

文件或数据库中将存储大约 100,000 个这样的条目。我想知道，返回与搜索匹配的结果及其关联的数值的最快方法是什么。

例如，查询“J”将返回 James 和 Jim 结果，最后一列中的数值。

我听人们提到二叉树搜索、字典搜索、索引搜索。我不知道哪个是阅读的好途径。

Answer 1

这是一个很难描述的问题。与许多优化问题一样，存在资源权衡。如果您确实想要尽可能最快的响应，那么一种可能的方法是将所有可能的搜索编译到准备好的结果表中，这样，给定搜索键，您就可以在表中查找搜索键并返回结果。

假设您的字符集仅限于 A-Z 和 a-z，则按照当今的标准，每个搜索键的条目包含 0 到 4 个字符的表将使用适量的内存。每个表条目中只需要有两个值:数值列表中的开始位置和结束位置。 (以这种方式编译列表:按名称字段对记录进行排序。仅从记录中提取数值，保持顺序，将它们放入列表中。任何搜索键都必须返回该列表中连续记录的子列表。这是因为搜索是针对名称字段的前缀字符串，因此当按名称字段排序时，与搜索键匹配的任何记录都是相邻的。)

因此，要创建一个表来查找 0 到 4 个字符的任意键，成对表中需要的条目少于 53⁴ 个，其中成对的每个成员都包含一个记录号(32 位或更少)。因此 8•534 = 60.2 MiB 就足够了。 (53 是因为您有 52 个字符加上一个标记字符来标记 key 的结尾。替代编码可以减少这一点。)

要支持超过 4 个字符的按键，您需要扩展它。对于典型数据，4 个字符将大大缩小搜索范围，因此您可以采用前 4 个字符指示的记录集并对其进行修剪以获得最终结果。如果数据存在病态情况，即 4 个字符并不能减少太多搜索量，您可以修饰此技术。

那么，这真的是您想要做的吗，让速度尽可能快，而不考虑其他资源(包括工程时间)的消耗？如果没有，您的实际目标是什么？