0

我有一组数据，它有一个名称、一些子值和一个关联的数值。例如：

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 结果，其中最后一列中的数值。

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

4

1 回答 1

1

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

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

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

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

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

于 2012-07-30T20:05:22.837 回答