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

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

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

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

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

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

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

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

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

 

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

 

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

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

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

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

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

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

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

 

Индексированные файлы

 

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

Пример,

пусть существуют две последовательности символов X₁X₂…X_k и Y₁Y₂…Y_m. Где каждый X и Y – отдельный символ. Можно утверждать, что X₁X₂…X_k < Y₁Y₂…Y_m в двух случаях:

1) k< m и X₁X₂…X_k = Y₁Y₂…Y_k

2) для некоторого i£ min(k, m) будет иметь место X₁=Y₁, X₂=Y₂, …, X_i-1=Y_i-1 и код X_i меньше кода Y_i. При этом в качестве кода может быть взят ASCII код символов.

Согласно этому принципу «свет» < «светлый» или «луг» < «лук».

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

В этом случае файл можно просматривать как обычный словарь или телефонный справочник, когда просматриваются лишь заглавные слова или фамилии на каждой странице. Чтобы облегчить процедуру поиска, можно создать второй файл, называемый разреженным индексом, который состоит из пар (x, b), где x - значение ключа, а b - физический адрес блока, в котором значение ключа первой записи равняется х. Разреженный индекс должен быть отсортирован по значениям ключей.

 

Пример,

на рисунке 7 показан основной файл, а так же соответствующий ему файл разреженного индекса.

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

 

 

Рисунок 7 – Основной файл и его разреженный индекс

 

Чтобы отыскать запись с заданным ключом х, надо сначала просмотреть индексный файл, отыскивая в нем пару (x, b). В действительности отыскивается наибольшее z, такое, что z x и далее находится пара (z, b). В этом случае ключ х оказывается в блоке b (если такой ключ вообще присутствует в данном файле).

 

⇐ Предыдущая12345Следующая ⇒

Поделиться: