Я плохо обьяснил :) Я имел в виду hash table. Скажем в C++ нужно для поиска номера записи по значению этого ID. Эту таблицу я назвал индексом. Обычно делают тупое соответсвие ID-->RecordNumber и всё грузят в hash table (или binary search map - не важно) Получается 200GB и полный облом. :) Простой вопрос - как уменьшить ее к примеру в 100 тысяч раз? :) Или в миллион? :)
Fixed size - не важно. Нужно по значению ключа найти номер записи. А какой алгоритм поиска дальше этой записи - это отдельный вопрос. Fixed size - к примеру, да, меньше проблем.
Скажем, 20 байт для record ID - слишком много, для 2^32 records хватит и 4 байт. Но все равно надо хранить record address, который тоже несколько байтов.
Разве что делать фрагментацию индекса, хранить его на диске по блокам, и загружать в память только релевантный блок.
Comments 7
Reply
Я имел в виду hash table.
Скажем в C++ нужно для поиска номера записи
по значению этого ID. Эту таблицу я назвал индексом.
Обычно делают тупое соответсвие ID-->RecordNumber
и всё грузят в hash table (или binary search map - не важно)
Получается 200GB и полный облом. :)
Простой вопрос - как уменьшить ее к примеру в 100 тысяч раз? :)
Или в миллион? :)
Reply
Нужно по значению ключа найти номер записи.
А какой алгоритм поиска дальше этой записи - это отдельный вопрос.
Fixed size - к примеру, да, меньше проблем.
Reply
Скажем, 20 байт для record ID - слишком много, для 2^32 records хватит и 4 байт. Но все равно надо хранить record address, который тоже несколько байтов.
Разве что делать фрагментацию индекса, хранить его на диске по блокам, и загружать в память только релевантный блок.
Reply
Reply
Reply
Leave a comment