Список поиска для объектов, действительных во временном интервале

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-100 тыс. Элементов в структуре, и мне бы хотелось, чтобы скорость ускоренного поиска была вставкой, а удаление может быть медленнее.

Элементы будут иметь повторяющиеся значения valid_from и valid_to, поэтому необходимо поддерживать дубликаты. Элементы будут перекрываться.

Мне нужно будет постоянно вставлять данные в структуру (вероятно, по массе для начальной загрузки, а затем одно обновление при изменении данных). Я также буду периодически модифицировать записи так, чтобы удалить и вставить.

Я не уверен, что лучший подход к этому является очень эффективным способом?

Алгоритмы не мои сильные костюмы, но если я просто знаю правильный подход, я могу исследовать сами алгоритмы.

Моя идея:

Первоначально я думал модифицированное бинарное дерево поиска для поддержки дубликатов ключей и ближайший поиск, но это только позволило бы мне запрашивать объекты, которые> valid_from или < valid_to.

Это потребует от меня деления пополам массива или дерева, чтобы найти все элементы> valid_from, а затем вручную проверить каждый из них на valid_to.

Я полагаю, что у меня могло бы быть два дерева поиска, одно для valid_to и valid_from, тогда я мог проверить, какие идентификаторы из результатов перекрываются и возвращать эти идентификаторы?

Это все еще кажется взломанным для меня? Есть ли лучший подход, который кто-то может порекомендовать или как это делается.

Answer 1

Представьте, что у вас есть два списка: инициация/начало и окончание/конец. Оба сортируются по TIME.

Учитывая конкретное время, вы можете найти, где в каждом списке первый элемент соответствует критериям бинарного поиска. Вы также можете вставлять бинарный поиск в каждый список.

Например, если есть 1000 предметов и начальное местоположение - 342, то возможны пункты 1-342, и если конечное местоположение 901, то возможны пункты 901-1000 в списке завершения. Теперь вам нужно пересечь оба подписок.

Взять идентификаторы предметов с 1-342 в начале и 901-1000 в конце и поместить их в отдельный массив (выделенный заранее). Сортировка массива. Переместите массив. Всякий раз, когда один и тот же идентификатор появляется дважды в строке, это попадание, действительное совпадение.