Здравствуйте.
У нас 2М (сконверченая geoip база). Памяти жрет много, да, но на скорость ответов практически не влияет.
Данные хранятся в radix tree. Поиск по ней не сильно зависит от количества префиксов и имеет прогнозируемое время.
Грубо говоря до 32 итераций для адресов /32.