Операции над хешированными файлами

Динамическое хеширование

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

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

Рисунок 6 – Динамическое хеширование

Для поиска записи с ключом v необходимо вычислить значение h(v) и считать соответствующий заголовок бакета. Затем необходимо проверить блоки бакета как блоки в файле, организованном в виде кучи. Если на каком либо шаге рассматриваемый блок имеет пустой указатель, а запись все еще не найдена, то нет необходимости просматривать остальные блоки файла, так как они не соответствуют значению хеш-функции указанного ключа.

Для вставки записи со значением ключа v необходимо вычислить значение h(v) и найти нужный бакет. Пустое место для вставки новой записи имеет только последний блок бакета. Поэтому необходимо просматривать блоки бакета, пока не дойдем до блока с пустым указателем. Существует две ситуации, в которых нет необходимости просматривать блоки бакета:

1. Если записи должны быть уникальны, то операции вставки будет предшествовать операция поиска. В случае если запись не найдена, то на момент завершения поиска считанным уже будет последний блок соответствующего бакета.

2. Если уникальность записей не важна, то каталог бакетов можно усилить, введя дополнительный массив указателей, содержащих указатели на последние блоки бакетов.

После того как нужный блок был найден, в него помещается новая запись и он записывается обратно на диск. Если последний блок не имеет свободного места под запись, то выделяется еще блок, в него помещается новая запись, а пустой указатель предыдущего блока меняется на адрес нового, и оба блока перезаписываются.

Если заголовок бакета уже содержит пустой указатель, то просто выделяется новый блок, и указатель на него помещается в заголовок бакета.

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

При модификации производиться поиск блока с соответствующей записью, если такой блок найден, то искомая запись в этом блоке модифицируется, и блок перезаписывается на диск.

Дата добавления: 2015-05-09