javascript - 在某个时间范围内有效的对象的搜索列表

Question

我有以下数据结构，它描述了一个对象及其有效时间段。假设下面的数字是 unix 时间戳。

{
  "id": 1234,
  "valid_from": 2000
  "valid_to": 4000
},
{
 "id": 1235,
 "valid_from": 1000,
 "valid_to": 2200,
}
...

我希望能够快速将这些项目存储在 JavaScript 中，然后查询在特定时间有效的项目。

例如，如果我要查询在 2100 有效的对象，我会得到 [1234, 1235]。如果我要查询在 3999 有效的对象，我会得到 [1234]，而在 4999 什么也没有。

我的结构中有大约 50-100k 项的大小，我希望查找速度快，但插入和删除速度可能会慢一些。

项目将具有重复的 valid_from 和 valid_to 值，因此它需要支持重复项。项目将重叠。

我需要不断地向结构中插入数据(可能是批量插入初始加载，然后随着数据变化一次性更新)。我还将定期修改记录，很可能是删除和插入。

我不确定高效的最佳方法是什么？

算法不是我的强项，但如果我知道正确的方法，我可以自己研究算法。

我的想法:

我最初想的是修改二叉搜索树以支持重复键和最近查找，但这只允许我查询 > valid_from 或 < valid_to 的对象。

这将涉及我将数组或树一分为二以找到所有项目 > valid_from，然后手动检查每个项目的 valid_to。

我想我可以有两个搜索树，一个用于 valid_to 和 valid_from，然后我可以检查结果中的哪个 ID 重叠并返回这些 ID？

这对我来说还是有点老套？是否有人可以推荐更好的方法，或者这是如何完成的。

Answer 1

假设您有两个列表:initiation/begin 和 expiration/end。两者均按时间排序。

给定一个特定的时间，您可以通过二分查找找到每个列表中第一项符合条件的位置。您还可以通过二进制搜索对每个列表进行插入。

例如，如果有 1000 个项目，开始位置为 342，则可能有项目 1-342，如果结束位置为 901，则可能有终止列表中的项目 901-1000。您现在需要将两个子列表相交。

从 begin 的 1-342 和 end 的 901-1000 中取出项目 ID，并将它们放在一个单独的数组中(提前分配)。对数组进行排序。遍历数组。每当相同的 ID 连续出现两次时，它就是一次命中，一次有效匹配。