Продолжение про задачку на сообразительность....

[febb]

https://febb.livejournal.com/3401072.html

Еще раз: имеется 4 миллиарда записей с уникальным ID к примеру 20 байт.
Таким образом один только индекс по идее должен занимать в памяти
(20 + 4)х4,000,000,000 = 96Gb, точнее больше с учетом накладных расходов.
Ни в какую память рельно не влезает. Как впихнуть его скажем в 1MB и меньше?

Решение никто не придумал, а оно крайне простое и удивительно эффективное...


Идея очень простая!

Разобьем ID примерно пополам, так что уникальных ID1 и ID2 будет примерно по 64K.
Сделаем две таблицы каждая по 64K х 10 байт, что примерно чуть больше 1 Мб.
А составной индекс будет просто из двух частей этих таблиц: ID1 << 16 + ID2
Скорость индексирования будет в несколько раз выше (может быть в 8 раз),
а размер индекса в память в 100,000 раз меньше!
Можно разбить и на 4 части и т.д. Есть метод как сделать это с гарантией.
Простое решение как видите и меня 15 лет назад это очень впечатлило.

Мне даже дали грамоту от владельца компании и премию в $250. :)))
Хахаха! Какое изощреное издевательство!
Через год я оттуда ушел...