Т.е. я так понимаю, оно пополняться не будет? Если нет — то можно сделать свой велосипед на основе flat файлов с фиксированными длинами полей. Будет быстрая выборка обычными seek. По необходимости [s]присыпать солью[/s] разбить на группы по N записей и хранить в отдельных файлах, именованных согласно (id / N), таким образом файловая система будет частично решать вопросы случайного поиска. Если еще дальше развивать идею, можно попробовать еще разбить по папкам (как например хранит кеш squid).
А если же это дело будет регулярно изменяться, то лучше SQL ничего не придумать. 2 Млн записей — не так уж много, тем более что не нужно по ключам выбирать.
