Хеш-таблицы во внешней памяти.

Определение

Хеш-таблицы во внешней памяти - это специальный тип хеш-таблиц, предназначенных для работы с данными, хранящимися на диске или других внешних носителях. Они используются для эффективного хранения и поиска больших объемов данных, которые не могут полностью поместиться в оперативной памяти компьютера

Весь файл разбит на три зоны.

• Первая зона — фиксированного размера, заголовок. В нём можно хранить такую информацию, как размер хеш-таблицы HASHSIZE, начало и размер второй зоны, количество записей в таблице, смещение в файле, по которому можно записывать новые данные, и проч.
• Вторая зона содержит точки входа — смещение в файле, по которому начинается поиск требуемой записи. В этой зоне находится HASHSIZE входов.
• Третья зона содержит сами записи. Каждая запись содержит три поля — ключ, данные и точку продолжения поиска при коллизии.

Особенности

• Внешняя память: Данные хранятся на диске или других внешних устройствах вместо оперативной памяти.
• Блочное чтение и запись: Вместо того, чтобы читать и записывать данные по одной записи, данные читаются и записываются блоками, что уменьшает количество операций ввода-вывода и повышает производительность.
• Использование индекса: Обычно хеш-таблицы во внешней памяти используют индексную структуру для быстрого доступа к блокам данных на диске.
• Алгоритмы разрешения коллизий: Используются алгоритмы разрешения коллизий, такие как метод цепочек или открытая адресация, но они адаптированы для работы с внешней памятью.

Преимущества

• Эффективность работы с большими объемами данных: Хеш-таблицы во внешней памяти позволяют эффективно хранить и обрабатывать данные, которые не помещаются в оперативной памяти.
• Ускоренные операции ввода-вывода: Использование блочного чтения и записи помогает уменьшить количество операций ввода-вывода, что увеличивает производительность работы с данными на диске.