Привет,


пишу на яве некий сетевой сервис и вот потребовалось сделать быстрый и компактный поиск по спискам IP адрессов/сетей.
Таких списков планируется много, клиет может настроить множество правил на разные сущности.

Встал вопрос компактности хранения отдельных списков IP адресов, а так же поиска по ним если список вдруг станет достаточно большим (пару тысяч сетей/адресов).

Кто что может посоветовать ? Если уже готовые велосипеды ? или какие наработки для таких алгоритмов ?

Буду рад любому ... так как я пока ничего толкового не придумал:

Если список маленький то перебирать поочерёдно ....
Если большой то строить Мар по сетям , а адреса конвертировать в сеть с маской /32 ...
а алгоритм поиска довольно простой искать сетку с маской /32 потом /31 ... и так далее..

Может проще строить бинарное дерево в памяти и бегать по нему ... (изменения в таком дереве только через перестройку его с начала )

Есть у кого идеи ?

Usman,

Спасибо !

Petro123KRED,
на что тратится у тебя рессурсы?
Если простой перебор, то пару тысяч элементов - это пустяк. Не усложняй.

Ты не повериш ... всё упирается в сетевой стек операционки :-) , но скоро будет все намного быстрее работать чем те жалкие 170к запросов в секунду что получается получить через ОС.

Но суть не в этом, а в том что мне нужно реализовать некую логику основаную на нахождении клиента в каком либо списке IP адресов.
Например GEO базаданных , например списки доступа ... например ещо что то связаное со списками Адрессов/сетей.

И так как такие операции будут очень частыыми (несколько проверок на один запрос) то я и задумался что будет лудше простого перебора.

Alex_1976для скорости IP сдвигом превращают в bigint
Как говориться все давно уже придумано.
Это примерно как логи ISA сервера, там в базе IP все bigint

немоглибы вы уточнить Вашу идею ?