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

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

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

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

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

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

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

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

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

1.7 Эффективность хешированных файлов

Основное положение эффективности хешированных файлов следующее. Все операции на хешированных файлах производятся в В раз быстрее (В – число бакетов), чем на файлах, организованных в виде кучи.

Пусть в файле храниться n записей, помещающихся в R блоков. Хеш-функция выбрана так, что число бакетов равняется B. Если при этом таблица бакетов находится в оперативной памяти, то потребуется следующее число доступов:

1)  n/2BR при успешном поиске, а также удалении и модификации существующей записи;

2)  n/BR при неудачном поиске, а также при проверке бакета перед вставкой, удалением и модификацией, если искомая запись отсутствует.

Основанием для таких расчетов служит тот факт, что в бакетах находится по n/R записей. Функция хеширования выбрана так, что записи в бакеты размещаются равномерно.

Если каталог бакетов находится на диске, то все количество доступов по всем операциям увеличивается на единицу, а в том случае, когда требуется внести изменения в каталог бакетов, на два.

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