通过范围内的多个参数搜索对象的高效设计
Efficient design to search for objects by multiple parameters with range
我在内存中有一组相同类型的对象，每个对象都有多个不可变的 int 属性（但不仅限于它们）。
我需要在那里找到一个（或多个）属性在指定值附近的小范围内的对象。例如。 a == 5+-1 && b == 21+-2 && c == 9 && any d.
存储对象的最佳方式是什么，以便我可以像这样有效地检索它们？
我考虑过为每个 属性 制作 SortedList 并使用 BinarySearch 但我有很多属性所以我想有一个更通用的方式而不是那么多 SortedLists.
重要的是集合本身不是不可变的：我需要 add/remove 项的能力。
对象（不仅仅是数据）是否有内存数据库之类的东西？
首先，有很多 SortedList 并不是糟糕的设计。它本质上是所有现代 RDBMS 解决相同问题的方式。
此外：如果有一种简单、通用、接近最优的方式来回答此类查询，RDBMS 就不会为相对复杂和缓慢的查询而烦恼查询计划优化技巧：即生成大量候选查询计划，然后启发式估计执行哪个计划所需的时间最少。
诚然，在 table 之间具有许多连接的查询往往会使 space 可能的计划在 RDBMS 的实践中变得庞大，而您这里似乎没有这些计划。但即使只有一个 table（对象集），如果有 k 个字段可用于选择行（对象），那么理论上你可以有 k！不同的索引（SortedLists of (key, value) pairs，其中键是 k 字段值的一些有序序列，值是例如指向对象的内存指针）可供选择。如果查询的结果是单个对象（或者，如果查询包含所有 k 个字段的非范围子句），则使用的索引无关紧要——但在所有其他情况下，每个索引通常会执行不同，因此查询规划器需要准确估计每个子句的选择性，以便选择要使用的最佳索引。
只是稍微扩展一下@j_random_hacker 的回答：'estimates of the selectivity' 的常用方法是为索引构建直方图。但是，您可能已经凭直觉知道哪个标准将产生 "a == 5+-1 && b == 21+-2 && c == 9" 中最小的初始结果集。很可能是 "c == 9"，除非 'c'.
的重复值数量特别多且潜在值的范围很小
因此，对谓词进行简单分析将是一个简单的起点。平等条件很可能是最具选择性的（表现出最高的选择性）。
从那时起，RDBMS 将对结果集中的记录进行顺序扫描，以过滤剩余的谓词。这可能也是您的最佳方法。
或者，有任意数量的内存中、占用空间小 SQL 的 DBMS 可以为您完成繁重的工作（eXtremeDB、SQLite、RDM、... google 是你的朋友）and/or 具有较低级别的接口，不会为你完成所有工作（仍然是大多数），但也不会将 SQL 强加给你。
我在内存中有一组相同类型的对象，每个对象都有多个不可变的 int 属性（但不仅限于它们）。
我需要在那里找到一个（或多个）属性在指定值附近的小范围内的对象。例如。 a == 5+-1 && b == 21+-2 && c == 9 && any d.
存储对象的最佳方式是什么，以便我可以像这样有效地检索它们？
我考虑过为每个 属性 制作 SortedList 并使用 BinarySearch 但我有很多属性所以我想有一个更通用的方式而不是那么多 SortedLists.
重要的是集合本身不是不可变的：我需要 add/remove 项的能力。
对象（不仅仅是数据）是否有内存数据库之类的东西？
首先，有很多 SortedList 并不是糟糕的设计。它本质上是所有现代 RDBMS 解决相同问题的方式。
此外：如果有一种简单、通用、接近最优的方式来回答此类查询，RDBMS 就不会为相对复杂和缓慢的查询而烦恼查询计划优化技巧：即生成大量候选查询计划，然后启发式估计执行哪个计划所需的时间最少。
诚然，在 table 之间具有许多连接的查询往往会使 space 可能的计划在 RDBMS 的实践中变得庞大，而您这里似乎没有这些计划。但即使只有一个 table（对象集），如果有 k 个字段可用于选择行（对象），那么理论上你可以有 k！不同的索引（SortedLists of (key, value) pairs，其中键是 k 字段值的一些有序序列，值是例如指向对象的内存指针）可供选择。如果查询的结果是单个对象（或者，如果查询包含所有 k 个字段的非范围子句），则使用的索引无关紧要——但在所有其他情况下，每个索引通常会执行不同，因此查询规划器需要准确估计每个子句的选择性，以便选择要使用的最佳索引。
只是稍微扩展一下@j_random_hacker 的回答：'estimates of the selectivity' 的常用方法是为索引构建直方图。但是，您可能已经凭直觉知道哪个标准将产生 "a == 5+-1 && b == 21+-2 && c == 9" 中最小的初始结果集。很可能是 "c == 9"，除非 'c'.
的重复值数量特别多且潜在值的范围很小因此，对谓词进行简单分析将是一个简单的起点。平等条件很可能是最具选择性的（表现出最高的选择性）。
从那时起，RDBMS 将对结果集中的记录进行顺序扫描，以过滤剩余的谓词。这可能也是您的最佳方法。
或者，有任意数量的内存中、占用空间小 SQL 的 DBMS 可以为您完成繁重的工作（eXtremeDB、SQLite、RDM、... google 是你的朋友）and/or 具有较低级别的接口，不会为你完成所有工作（仍然是大多数），但也不会将 SQL 强加给你。