Я сегодня много думал.
Думал о битсетах и Блум-фильтрах.
Захотелось мне создать Блум-фильтр-лайк структуру, по которой можно было бы итерироваться.
То есть вот буквально 3 операции. Добавить индекс, проверить наличие и проитерироваться.
С возможностью получить ложно положительные результаты в двух последних.

И вот идея.
Наверное многие из нас знакомы с иерархическими битсетами. Где мы ставим биты на нижнем уровне для отдельных индексов, а выше для все больших диапозонов, и так 3-4 и более уровней.
При итерации мы пропускаем огромные диапазоны если бит не выставлен. А если выставлен, то смотрим биты суб-диапазонов, спускаемся все ниже до отдельных индексов на каждый бит.

И все бы ничего, но нам надо памяти по 1 биту на каждый возможный индекс. Ну да, лениво выделяя ее по возможности, но со временем вот так много.
А что если разных значений мы выставить можем миллиард, но одновременно лишь сотни?

Как насчет использовать Блум-фильтр на каждом уровне? Сильно меньше чем целый бит на возможный индекс, а стремиться к 2 * сколько одновременно храним индексов.
А итерируемся так же. Просто с ложными индексами с небольшой вероятностью (пока не переполнили слишком фильтр).

Грубые подсчеты говорят, что должно быть сильно экономно.