高效设计多参数范围搜索对象

Question

我在内存中有一组相同类型的对象，每个对象都有多个不可变的int属性（但不仅仅如此）。

我需要查找那些属性在指定值附近范围内的对象（一个或多个）。例如 a == 5+-1 && b == 21+-2 && c == 9 && 任何d。

最好的方法是如何存储这些对象，以便我可以高效地检索它们？

我考虑过为每个属性制作SortedList，并使用BinarySearch，但是我有很多属性，所以希望有更通用的方法，而不是这么多SortedList。

重要的是集合本身不是不可变的：我需要能够添加/删除项。

是否存在像内存数据库一样的东西（不仅仅是数据）？

- Vlad

---

尝试使用SortedDictionary<int, object>或SortedDictionary<int, List<object>>。 - jdweng

@jdweng，但是我需要十个字典（每个属性一个）和一个代码来连接找到的结果。非常繁琐！ - Vlad

拥有大量的列表并不意味着某个东西不是通用的。你正在考虑的方法听起来很有前途，所以继续实现它; 并非所有东西都是内置的。 - Ry-

Answer 1

首先，拥有大量的SortedList并不是不好的设计。这本质上是所有现代RDBMS解决相同问题的方式。

进一步说：如果存在一种简单、通用、接近最优效率的方法来回答这些查询，RDBMS就不会费心去处理相对复杂和缓慢的查询计划优化：也就是生成大量候选查询计划，然后启发式地估计哪个计划执行时间最短。

不可否认的是，在关系型数据库系统中，表之间连接较多的查询往往会使得可能的计划空间非常巨大，但你似乎在这里没有这种情况。即使只有一个表（一组对象），如果有k个字段可以用于选择行（对象），则理论上可以有k!不同的索引（SortedList）来选择，其中键是某些k字段值的有序序列，而值是指向对象的内存指针。如果查询的结果是单个对象（或者，如果查询包含所有k个字段的非范围子句），则使用的索引不重要——但在其他每种情况下，每个索引通常会有不同的性能表现，因此查询规划器需要准确估计每个子句的选择性才能选择最佳的索引。

- j_random_hacker

Answer 2

为了进一步扩展@j_random_hacker的答案：通常估计选择性的方法是为索引构建直方图。但是，您可能已经直观地知道哪个条件将产生最小的初始结果集，例如“a == 5+-1 && b == 21+-2 && c == 9”。最有可能的是“c == 9”，除非存在异常高数量的重复值和潜在值域较小的情况下。

因此，对谓词进行简单分析是一个容易入手的起点。相等条件极有可能是最具选择性（表现出最高的选择性）。

从那时起，RDBMS将对结果集中的记录进行顺序扫描，以过滤剩余的谓词。这也许是您最好的方法。

或者，有许多内存中、占用空间小且支持SQL的DBMS可以为您完成繁重的工作（如eXtremeDB、SQLite、RDM等，Google是您的朋友），或者具有较低级别的接口，不会为您完成所有工作（仍然是大部分），但也不会强制实施SQL。

- Steven Graves