选择哪个DB来查找最佳匹配记录？

Question

我将对象存储在由许多整数属性描述的数据库中.真实的对象有点复杂,但现在让我们假设我在我的数据库中存储汽车.每辆车都有很多整数属性来描述汽车(即最大速度,轴距,最大功率等),这些属性可由用户搜索.用户为每个对象定义了一个首选范围,因为有很多属性,所以很可能不会有任何匹配所有属性范围的汽车.因此,查询必须返回按最佳匹配排序的多个汽车.

目前我使用以下查询在MySQL中实现了这一点:

SELECT *, SQRT( POW((a < min_a)*(min_a - a) + (a > max_a)*(a - max_a), 2) +
                POW((b < min_b)*(min_b - b) + (b > max_b)*(b - max_b), 2) +
                ... ) AS match
WHERE a < (min_a - max_allowable_deviation) AND a > (max_a + max_allowable_deviation) AND ...
ORDER BY match ASC

其中a和b是对象的属性,min_a,max_a,min_b和max_b是用户定义的值.基本上,匹配是期望范围与属性的实际值之间的平方差之和的平方根.值0表示完美匹配.

该表包含几百万条记录,并且仅引入WHERE clausule以限制执行计算的记录数.索引放在所有可查询记录上,查询大约需要500ms.我想改进这个数字,我正在研究改进这个查询的方法.

此外,我想知道是否会有更适合执行此工作的不同数据库.此外,由于其更灵活的数据方案选项,我非常希望更改为NoSQL数据库.我一直在研究MongoDB,但找不到有效(快速)解决这个问题的方法.

有没有比MySQL更适合这项工作的数据库？

Answer 1

看一下R 树。（有关特定变体的页面提供了更多详细信息并提供了伪代码）。这些数据结构允许您通过边界矩形进行查询，这就是按每个属性的范围进行搜索的问题所在。

将您的汽车视为 n 维空间中的点，其中 n 是描述您的汽车的属性数量。然后给定一个范围，每个范围描述一个属性，问题是找到该 n 维超矩形中包含的所有点。R 树有效地支持此查询。MySQL为其空间数据类型实现了R树，但MySQL仅支持二维空间，这对您来说是不够的。我不知道有任何现成的支持 n 维 R 树的常见数据库，但您可以采用一些对用户定义的树数据结构有良好支持的数据库，并在此基础上自己实现 R 树。例如，您可以为 MongoDB 中的 R 树节点定义一个带有子指针的结构。然后，您将在自己的代码中实现 R 树算法，同时让 MongoDB 负责存储数据。

另外，还有一个实现 R 树的C++ 头文件，但目前它只是一个内存结构。尽管如果您的数据集只有几百万行，那么在启动时加载此内存结构并在添加新车时更新它似乎是可行的（我认为这种情况很少见）。