Привет всем. Столкнулся тут с одной проблемой. У меня есть большой

Question

Привет всем. Столкнулся тут с одной проблемой. У меня есть большой

файл, где находятся строки c двумя полями типа timestamp и другими полями числового типа.
По факту моя задача сводится к банальному поиску по двум колонкам в промежутке, если бы речь шла про SQL запрос:

SELECT ...
WHERE start_date >= ... AND end_date <= ...

Достаточно оптимальным способ тут будет построение так называемого generalized search tree (aka GiST).
Под капотом же в том же постгрессе есть расширение и для времени, которое уже позволяет строить R-деревья: https://postgrespro.com/blog/pgsql/4175817

В общем, хотелось бы избежать лишнего сканирования файла, но для этого мне нужна грамотная структура в памяти. Не посдскажите, подойдёт ли мне тут R-дерево?
И если да - то какую джавовую библиотеку посоветуете? Желательно с поддержкой канкаренси и LRU.

#backend #java #programming #russian

0

04.12.2021

8 ответов

24 просмотра

Aleksandr Автор вопроса

Alexander Biryukov
https://en.m.wikipedia.org/wiki/Interval_tree#:~:t...

О нем и речь. Он строится на r-деревьях.

0

04.12.2021

Alexander Biryukov

Aleksandr
О нем и речь. Он строится на r-деревьях.

Дерево интервалов можно сделать на AVL/RB-дереве, не обязательно обобщать до R-деревьев. https://github.com/Breinify/brein-time-utilities из готового, но мы не написали свое, т.к. время как long timestamp'ы храним, и проще самим на примитивах было сделать.

0

04.12.2021

Denis Pavlyuchenko

а альтернативное решение не рассматривалось? взять sqlite, загрузить туда файл и написать этот самый запрос

0

05.12.2021

Mark Andreev

Denis Pavlyuchenko
а альтернативное решение не рассматривалось? взять...

Кстати, не многие знают, но Clickhouse можно запускать в режиме cli, без поднятия полноценного сервера. При этом с файлами можно работать с помощью табличного движка File. https://clickhouse.com/docs/ru/operations/utilities/clickhouse-local/amp/

0

05.12.2021

Aleksandr Автор вопроса

Denis Pavlyuchenko
а альтернативное решение не рассматривалось? взять...

Не могу в задаче использовать субд, увы.

0

05.12.2021

Sergey Bezrukov

Aleksandr
Не могу в задаче использовать субд, увы.

Почему? Вы же спрашивали про либу для дерева, вот in-memory h2 и будет такой либой ) Она же встраиваемая в процесс, т.е. отдельно её запускать не надо.

0

05.12.2021

Aleksandr Автор вопроса

Sergey Bezrukov
Почему? Вы же спрашивали про либу для дерева, вот ...

Хм, а про какую именно либу идёт речь?

0

05.12.2021

Alexander Biryukov · Accepted Answer

Alexander Biryukov

https://en.m.wikipedia.org/wiki/Interval_tree#:~:text=In%20computer%20science%2C%20an%20interval,any%20given%20interval%20or%20point.&text=intervals%20containing%20a%20given%20query,for%20a%20very%20simple%20one). Не проще будет? Если речь только об интервалах

0

04.12.2021

170 похожих чатов

Привет всем. Столкнулся тут с одной проблемой. У меня есть большой

8 ответов

Похожие вопросы