Хранилище должно потреблять по возможности меньше оперативной памяти и работать быстро.
Если «быстро», значит все данные должны находиться в оперативной памяти. Сколько ее потребуется? Примем, что средняя длина доменного имени 30 символов (уверен, это с большим запасом). Если их хранить просто как текст, нужно 30 байт. Еще 3 байта на число, 1 байт на длину строки, итого 33 байта на запись. Для двух миллионов записей потребуется около 63 Мб. Столько оперативной памяти
придется выделить для быстрой работы. Значит мы можем минимизировать только оверхед по памяти, обусловленный выбором того или иного «движка» для нашего хранилища. Отсюда вывод: лучшее хранилище — простой массив, загружаемый из простого текстового файла. Генерируем последовательность псевдослучайных чисел и делаем выборку из массива по индексам.
Если память действительно критична, то можно подумать о более компактном представлении доменных имен (словарь TLD, точки и т.п.)