Дальнейшая оптимизация возможна, но неуниверсальными методами. Например, с помощью секционирования индекса по диапазонам ключей. Или созданием специального алгоритма хэширования. А вообще с подобными задачами обычно хорошо справляется database engine какой-нибудь. Sqlite, например.
В поисках упорядоченного множества в Python: разбираемся с теорией и выбираем лучшую реализацию