Есть база IP2Location. Пока - в текстовом файле.

Возникла мысль, как-бы ускорить по ней поиск. Т.е. стоит задача - по заданному IP адресу найти локацию как можно быстрее.

Описание полей:

FIELD # FIELD NAME DATA TYPE FIELD DESCRIPTION1 IP_FROM NUMERICAL (DOUBLE)Beginning of IP address range. The data is represented in IP number1 format.2IP_TO NUMERICAL (DOUBLE)Ending of IP address range. The data is represented in IP number1 format.3 COUNTRY_CODE CHAR(2) Two-character country code based on ISO 3166.4 COUNTRY_NAME VARCHAR(64) Country name based on ISO 3166.5 REGION VARCHAR(128) Region name.6 CITY VARCHAR(128) City name.7 LATITUDE NUMERICAL (DOUBLE) City latitude. Default to capital city latitude if city is unknown. 8 LONGITUDE NUMERICAL (DOUBLE) City longitude. Default to capital city longitude if city is unknown.9 ISP_NAME VARCHAR(256) Internet Service Provider registered under the IP address range.10 DOMAIN_NAME VARCHAR(128) Domain name assigned to Internet network.

Вот фрагмент таблицы локаций
Использование в БД - как-то некрасиво. Индексы дают логарифмическое время поиска и кроме того неэффективно работают с интервалами.

Я ищу время поиска близкое к константе и реализацию - в виде C++ библиотеки.

Делитесь мыслями. Я приветствую мозговой штурм.

k0rvinгм... использовать ипы в качестве индексов массива? правда массив получается весьма большой.

у хеш-таблиц какое время доступа?
При отсутствии промахов - константа. Теория говорит, что правильно выбранное соотношение ключей/элементов гарантирует попадание практически в 99.9%.

tanglirmaytonЯ ищу время поиска близкое к константеувы, при таких требованиях на ум приходит только libastral...
Спасибо, я там уже был.

Моя мысль - в другом направлении. Как оптимально искать интервалы (отрезки) в диапазоне DWORD ? GeoIP - всего-лишь практическое применение. Я пока не собираюсь устраивать бенчмарки я-vs-maxmind. Интерес - в поиске подходящего метода индексирования.

netwindкстати, и с базой не так все страшно,как вы думаете
все там вполне эффективно, при некоторых ухищрениях
http://sql.ru/forum/actualthread.aspx?tid=772393
Я понял направление. Вы думаете что RDBMS оптимально исполнит это?

?tid=772393EXPLAIN SELECT * FROM GeoIP WHERE startIpNum <=1834451198 AND endIpNum >=1834451198

Я к сожалению не умею интерпретировать планы MySQL, но если просветите, что делает ядро исполняющей машины для такого курсора - буду рад.

eNosemayton,

БерклиДБ.
в чистом виде: хэш-значение.
(отхлёбывая пиво)

Я тоже думал о Бекли. Это всего-лишь исполняющая машина которая юзает алгоритмы поиска Hash и BTree. Но эффективность решения в базе Беркли будет СИЛЬНО зависеть от того в КАКОМ ВИДЕ мы подадим на вход значения пары IP_FROM - IP_TO.

Есть конечно тривиальное решение. Все четыре миллиарда IP номеров забиваем ключами в хеш-таблицу. Но это оверхедно по памяти и глуповато. Мы не учитывает кусочно-линейный характер данных.

Кроме того, как быть с IPv6 в подобном примере. Я, как видите, смотрю в будущее...

Да. Я думал об этом. Надо поисследовать как диапазоны адресов распределены по сегментам. Всегда-ли он отображается 1:1. Если это так - то алгоритм действительно сильно упощается.

Эххх... придётся всё-таки грузануть это в базу.

Ладно. Всем - до завтра.

Диапазоны вроде-бы не пересекаются. Но сегменты сеток не такие ровные. Или мне по крайней мере в некоторых Locations не удаётся выделить диапазон хостов так гладко, как пишут в умных книжках по проектированию сетей.