通过多个参数和范围搜索对象的高效设计
本文关键字：对象 高效 搜索 范围 参数 | 更新日期: 2023-09-27 18:32:49
我在内存中有一组相同类型的对象，每个对象都有多个不可变的int属性(但不仅仅是它们(。
我需要在那里找到一个对象(或多个对象(，其属性在指定值附近的小范围内。 例如 a == 5+-1 && b == 21+-2 && c == 9 && any d .
存储对象以便我可以像这样有效地检索它们的最佳方法是什么？
我想过为每个属性制作SortedList并使用BinarySearch但我有很多属性，所以我想有一种更通用的方式而不是那么多SortedLists。
重要的是，集合本身不是不可变的：我需要添加/删除项目的能力。
对象(不仅仅是数据(是否有类似内存数据库的东西？
只是为了稍微扩展一下@j_random_hacker的答案："选择性估计"的常用方法是为指数构建直方图。 但是，您可能已经直观地知道哪些标准将产生"a == 5+-1 && b == 21+-2 && c == 9"的最小初始结果集。 最有可能的是"c == 9"，除非"c"的重复值数量特别多，潜在值范围很小。
因此，对谓词进行简单的分析将是一个简单的起点。 相等条件很可能是最具选择性的(表现出最高的选择性(。
从那时起，RDBMS 将对结果集中的记录进行顺序扫描，以过滤剩余的谓词。 这可能也是你最好的方法。
或者，有任意数量的内存中，占用空间小的SQLDBMS将为您完成繁重的工作(eXtremeDB，SQLite，RDM,... 谷歌是你的朋友(和/或具有较低级别的接口，这些接口不会为您完成所有工作(仍然是大多数(，但也不会将SQL强加给您。
首先，拥有大量的SortedList设计还不错。 它本质上是所有现代RDBMS解决相同问题的方式。
此外：如果有一种简单、通用、接近最优的方法来回答此类查询，RDBMS就不会为查询计划优化的相对复杂和缓慢的黑客而烦恼：即生成大量候选查询计划，然后启发性地估计哪个查询计划需要最少的时间来执行。
诚然，在 RDBMS 的实践中，表之间有许多连接的查询往往会使可能计划的空间变得巨大，而您在这里似乎没有这些。 但即使只有一个表(对象集(，如果有 k 个字段可用于选择行(对象(，那么理论上你可以有 k！不同的索引(SortedList S的(键，值(对，其中键是K字段值的某个有序序列，并且该值是例如指向对象的内存指针(可供选择。 如果查询的结果是单个对象(或者，如果查询包含所有 k 字段的非范围子句(，则使用的索引无关紧要 - 但在所有其他情况下，每个索引通常都会执行不同的性能，因此查询计划器需要准确估计每个子句的选择性，以便选择要使用的最佳索引。