Комментировать

С 500м это я конечно

С 500м это я конечно погорячился, даже и 250м не реально, реально 100м, поскольку элемент меньше 8 байт иметь не будет (4 на ключ, 4 на индекс/указатель). Но это ладно, гораздо интересней поиск.
Бинарный конечно не катит.
А если 32-арный? Т.е. данные представляются как 32-арное дерево, с 32 потомками каждого узла. Тогда каждый процессор (тред) может обрабатывать своего потомка, а результат всего варпа подаем на вход следующей итерации. Таким образом за 2 итерации можно выбрать из 1024 альтернатив, соответственно за 5 итераций можно выбрать из реально максимального 32м массива.
У этой идеи есть одна приятная особенность. Если выделить дополнительную память и в нее перезаписать каждый 32 элемент, то в каждой итерации поиска необходимые для работы данные можно подгружать в шеред память быстро по блокам.