搜索文件并返回值 – 超快速

我有一组数据,它们有一个名称,一些子值,然后是一个关联数值。 例如:

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结果,这些结果是最后一列中的数值。

我听说有人提到二叉树搜索,字典搜索,索引搜索。 我不知道哪条路是好的方法。

这是一个很难表征的问题。 与许多优化问题一样,资源也需要权衡。 如果您真的希望尽可能快地响应,那么可能的方法是将所有可能的搜索编译到准备结果表中,这样,给定搜索键,您可以在表中查找搜索键并返回结果。

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

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

要支持超过4个字符的键,您需要扩展它。 对于典型数据,4个字符会大大缩小搜索范围,因此您可以获取前4个字符所指示的记录集并修剪它以获得最终结果。 如果数据具有病态情况,其中4个字符不会大大减少搜索,则可以修饰此技术。

那么,这真的是你想要做的,尽可能快地提高速度,不管消耗的其他资源(包括工程时间)如何? 如果没有,你的实际目标是什么?