Лекция 5

Хеширование

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

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

Недостатки хеширования – необходимость выполнения самой операции свертки, борьба с возникновений коллизий. Свертка различных значений может дать одинаковый хеш код.

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

Главным ограничением этого метода является фиксированный размер таблицы. Если таблица заполнена слишком сильно или переполнена, возникает слишком много цепочек переполнения, и главное преимущество хеширования, доступ к записи почти всегда за одно обращение к таблице, будет утрачено. Расширение таблицы требует ее полной переделки на основе новой хеш функции (со значением свертки большего размера).

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

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

Рассмотрим организацию индексирования таблиц двумя схемами: одноуровневой и двухуровневой.

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

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

1. Образование свертки значения ключевого поля искомой записи.

2. Поиск в индексном файле записи о блоке, значение свертки которого больше или равно искомому.

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

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

На практике для создания индексов пользователь указывает поле некоторой таблицы базы данных, которая требует индексации. … во многих СУБД индексируется автоматически, такие индексы обычно называются первичными индексами. Индексы, создаваемые пользователем не для ключевых полей, называют вторичными пользовательскими индексами. Создание таких индексов не изменяет физического расположения записей таблицы, но влияет на последовательность просмотра записей. Связь вторичного индекса с элементами данных может быть установлена различными способами. Один из них - использование вторичного индекса для получения первичного ключа, по которому затем с использованием первичного индекса производится поиск необходимых записей.

В некоторых СУБД деление индексов на первичные и вторичные не производится. В этом случае используются автоматически создаваемые индексы и индексы, определяемые пользователем по любому из неключевых полей.