在時間範圍內有效的對象的搜索列表

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_from，然後手動檢查每個valid_to。

我想我可以有兩個搜索樹，一個用於valid_to和valid_from，然後我可以檢查結果中的哪個id重疊並返回這些id的？

對我而言，這仍然顯得有點不可靠嗎？有沒有更好的方法可以推薦或者是這樣做的。

Answer 1

想象一下你有兩個列表：啓動/開始和到期/結束。兩者都按TIME排序。

給定一個特定時間，您可以在每個列表中找到第一個項目符合二進制搜索條件的位置。您也可以通過二進制搜索插入到每個列表中。

例如，如果有1000個項目且開始位置是342，則項目1-342是可能的，並且如果結束位置是901，則終止列表中的項目901-1000是可能的。你現在需要交叉兩個子列表。

開始時從1-342開始取物品ID，最後取901-1000，並將它們放在單獨的數組中（提前分配）。對數組進行排序。遍歷數組。每當相同的ID連續出現兩次時，它就是一個有效的匹配。