Добрый день. Есть задача по хранению таблицы IP (IPv4) адресов при анализе трафика. Суть её в следующем, пришел пакет от какой либо сети, сохраняем IP адрес только конечного получателя т.е. клиента, далее по таблице IP адресов нужно ОЧЕНЬ БЫСТРО найти ячейку памяти для данного IP адреса и записать в таблицу там находящуюся количество принятого или полученного трафика. Вся задача реализации в том что бы обеспечить ОЧЕНЬ БЫСТРОЕ нахождение ячейки памяти для конкретного IP адреса. Думал, что сверх быстрым решение будет собственно массив в котором конкретный IP адрес будет индексом, но тут дело в том, что бы создать такой массив нужно будет 4 гб памяти только для указателей т.е. IP адрес представляется в виде 32 битного числа. В этом случае у сервера должно быть памяти в 8 гигабайт минимум скажем, но это мне кажется перебор хотя тоже вариант. Второе решение заключает в следующем - IP адрес уже разбит на 4 части т.е. 255(A).255(B).255(C).255(D) соответственно создать матрицу в которой будет находится таблица, и осуществлять в ней поиск поэтапно т.е. сначала найти ссылку на часть B по части A, потом на часть C по части B и т.д. в этом случае поиск участка памяти для конкретного IP адреса будет осуществляться в 4 этапа. При такой реализации не требуется 4 гб памяти но в скорости поиска эта реализация медленнее. При этом известно какие именно IP адреса будут присутствовать в таблице исходя из указания маски IP адресов (маски сети). Вопрос в следующем: эффективны ли такие организации решения задачи а насколько они вменяемые, существуют ли лучшие решения подобной задачи ? Спасибо.
Берем одномерный массив значений, где индексами будут служить значения IP деленные на некоторое достаточно небольшое простое число (например 65599). Таким образом получаем набор линий, значения по которым будут распределяться достаточно равномерно. А уже получив конкретную линию осуществить поиск по значениям в ней. Возможное улучшение - сортировать значения внутри линии. тогда можно искать в ней методом биения пополам. но скорость при сортировке не очень. Другой вариант - AVL (сбалансированное дерево) по A, в дочерних узлах по B и т.д. Причем при создании узла выделять память не у системы, а в заранее выделенных блоках памяти (свой мини менеджер памяти) для увеличения скорости.
