Структура данных для хранения диапазонов IP-адресов, обеспечивающая быстрый поиск данного IP-адреса (Java)

Если диапазоны не содержат поддиапазонов, вы можете проверить guava RangeSet.
https://code.google.com/p/guava-libraries/wiki/NewCollectionTypesExplained#RangeSet
На самом деле я не анализировал временную и пространственную сложность RangeSet, но RangeSet, похоже, удовлетворяет ваши требование вполне хорошо.

Я использую дерево AVL с диапазоном IP-адресов в качестве значения узла и подходящей функцией сравнения. (Если диапазон равен a..b (a ‹= b), при сравнении двух диапазонов r1 и r2: r1‹ r2, если r1.b ‹r2.a; r1" == "r2, если r1.a> = r2. a и r1.b ‹= r2.b; r1> r2, если r1.a> r2.b. Таким образом," == "означает, что r1 равно или входит в r2.)

Если у вас нет совпадений, этого достаточно. Если у вас есть перекрытия (как у меня, но я обрабатываю сетевые префиксы), вы получите деревья AVL, вложенные в деревья AVL.

Когда вы говорите, что нет перекрытия сетевых блоков ASN, я предполагаю, что если ASN имеет делегированный ему / yy, вы разбиваете родительский / xx на отдельные, но непрерывные сетевые блоки.

Поскольку ваш список сетевых блоков не так часто меняется, вам, вероятно, не нужно дерево AVL. Вы можете просто отсортировать сетевые блоки и попасть в список с помощью двоичного кода. Если вам нужно что-то, что работает быстрее, чем двоичное дерево / чоп, у вас может быть вспомогательный набор указателей в двоичный фрагмент, используя ms-байт начала просматриваемого диапазона, чтобы идентифицировать первый и последний диапазоны, которые стоит посмотреть в.

Это структура, которую я использую. Давайте возьмем другую таблицу, в данном случае таблицу locations, чтобы увидеть назначение и использование диапазонов IP-адресов в реальной ситуации.

--
-- Table structure for table `locations`
--
CREATE TABLE IF NOT EXISTS `locations` (
  `location_id` int(10) unsigned NOT NULL,
  `parent_id` int(10) unsigned NOT NULL,
  `location_name` varchar(64) NOT NULL,
  PRIMARY KEY (`location_id`),
  KEY `parent_id` (`parent_id`)
);

--
-- Table structure for table `locations_to_ip_ranges`
--
CREATE TABLE IF NOT EXISTS `locations_to_ip_ranges` (
  `l_ip_r` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `location_id` int(10) unsigned NOT NULL,
  `starting_ip` varchar(45) NOT NULL,
  `ending_ip` varchar(45) NOT NULL,
  `starting_cidr` int(10) unsigned NOT NULL,
  `ending_cidr` int(10) unsigned NOT NULL,
  PRIMARY KEY (`l_ip_r`),
  KEY `location_id` (`location_id`)
);

Вот несколько записей из второй таблицы

l_ip_r  location_id starting_ip     ending_ip        starting_cidr  ending_cidr
-------------------------------------------------------------------------------
94005   47          217.147.0.0     217.147.15.255   3650289664     3650293759
94004   47          217.146.32.0    217.146.47.255   3650232320     3650236415
94003   47          217.145.144.0   217.145.159.255  3650195456     3650199551
94002   47          217.145.16.0    217.145.31.255   3650162688     3650166783
94001   47          217.144.176.0   217.144.191.255  3650138112     3650142207

Следующая полезная функция для преобразования IP-адреса в номер CIDR. Он написан на PHP, но я считаю, что его будет легко преобразовать в Java. Используемая здесь функция explode() разделяет строку в соответствии с заданным разделителем.

function ip_address_to_cidr($ip_address){
    $ips = explode(".", $ip_address);
    return ($ips[3] + $ips[2] * 256 + $ips[1] * 65536 + $ips[0] * 16777216);
}

Итак, если вы хотите получить страну для данного IP-адреса, у вас будет что-то вроде этого

// call the ip_ip_address_to_cidr function passing the remote_address as an argument
$cidr = ip_address_to_cidr($_SERVER['REMOTE_ADDR']);

// pass the returned $cidr to the following query and get the location_id
$set = mysql_query("
    SELECT location_id 
    FROM locations_to_ip_ranges
    WHERE " . $cidr . " BETWEEN starting_cidr AND ending_cidr
");
$row = mysql_fetch_object($set);
echo $row->location_id 

Поскольку мне нужна многоязычная поддержка, есть еще одна таблица locations_to_languages, которую я не упомянул, чтобы она оставалась простой и понятной. В настоящее время эти таблицы содержат десятки миллионов данных, и у меня нет проблем с производительностью.

Боковое примечание: я давно не использую Java, поэтому приведенный выше фрагмент написан на PHP, но я считаю, что будет несложно понять логику и при необходимости преобразовать ее в Java.

Мы можем использовать btrees, с помощью которых мы можем сопоставить IP-адрес в первичной памяти, а затем сопоставить их с вторичной памятью. Как мы знаем, нам нужно хранить довольно большое количество IP-адресов, мы не можем хранить их в первичной памяти, как есть, лучше, если бы мы использовали btree. Поскольку это похоже на принцип хеширования, также эффективное использование памяти.