针对+ 5M记录表的快速，内存范围查找

我有一个包含+ 5M静态记录的数据库表。 结构简单:(从int开始，结束int，结果int）。 所以我有一个特定的INT，我需要找到它的相应结果（int）。 目前，查找表位于DB中，但它需要驻留在内存中，很可能位于没有数据库访问的环境中。

我的解决方案需要执行此逻辑而无需数据库访问，内存和超快速，因为我需要每秒处理1000次事务。 该集的大小略高于50MB，因此我可以将整个内容扔进内存并针对它运行范围查找，按照以下post： 在C＃中进行范围查找 – 如何实现 。 但我不知道它将如何在如此规模上发挥作用。

• 我是否“在启动时”预加载该表？ 这可能需要一段时间。
• 有什么方法可以将表加载到某个.dat文件中并在运行时进行超高效的查找？

顺便说一句，我在Azure上，不确定使用存储表是否有助于查找…

Answer 1

二进制搜索超快。 对50M记录进行二分查找只需要进行27次比较即可找到答案。 只需将其加载到内存中并使用您链接的Range查找。

如果发现它很慢，请开始优化：

• 将Range对象更改为struct而不是class
• 手动编码您自己的二进制搜索算法，（a）直接实现相等比较器，而不是调用IEqualityComparer ，（b）使用指针和其他不安全技巧在搜索时禁用数组边界检查。

Answer 2

您链接的范围查找代码执行二进制搜索，因此性能将为O(log n) 。 我不认为你可以做更好的范围查找。 HashSet的查找是O（1），但您不能将该结构用于范围查找。

500万条记录确实不是很大。 我建议您使用您将在生产中使用的硬件链接到的代码实现概念validation，并测量性能。

Answer 3

您当然可以将其放在顺序文件中并在启动时加载它。 在不到一秒的时间内，50 MB将从磁盘上脱落。 即使您必须将其解析为文本文件，您也应该能够在另一秒内创建表。 当您使用2 GHz（或更快）处理器处理它们时，500万条记录并不是那么大。

列表的二进制搜索是O（log n），因此每次搜索你将进行的探测的最大数量是24.这将是非常快速的。

它应该很容易加载这样的测试。 只需将其旋转，然后查看完成1,000,000次查找需要多长时间。 就像是：

 var clock = Stopwatch.StartNew(); for (int i = 0; i < NumIterations; ++i) { int val = GetRandomValueToSearchFor(); // however you do that Ranges.BinarySearch(val, RangeComparer); } clock.Stop(); // time per iteration is clock.TotalMilliseconds/NumIterations 

这将让你找出最快的查询事物。 我怀疑你每秒可以处理成千上万的交易。