С>Вам это наверное для какой-то более утилитарной задачи нужно?

Ничего сложного
Мне нужно сформировать файл на диске

Где для каждого ID от 0 до 0x5000000 хранится небольшой блок данных (от 0 до 80 байт, но может быть и больше)

Проблема в том, что блоки данных для каждого ID дополняются (увеличиваются) в случайном порядке

Скорость поиска и добавления должна быть максимальной
Что-то вроде обращения по индексу в массив
B-дерево не подходит

После завершения создания файла, больше ничего добавляться не будет
То есть промежуточные временные структуры (битмапы) можно хранить в памяти, а потом удалить

С>Вам это наверное для какой-то более утилитарной задачи нужно?

Ничего сложного
Мне нужно сформировать файл на диске

Где для каждого ID от 0 до 0x5000000 хранится небольшой блок данных (от 0 до 80 байт, но может быть и больше)

Проблема в том, что блоки данных для каждого ID дополняются (увеличиваются) в случайном порядке

Скорость поиска и добавления должна быть максимальной
Что-то вроде обращения по индексу в массив
B-дерево не подходит

После завершения создания файла, больше ничего добавляться не будет
То есть промежуточные временные структуры (битмапы) можно хранить в памяти, а потом удалить

---

Количество ID известно заранее

Вероятность что у ID блок данных умеет столько записей:
0 = 20%
1 = 40%
2 = 20%
3 = 10%
4 = 5%
5 = 2%
...