2. Индексирование и хеширование

2.1. Индексы и их использование для ускорения извлечения данных

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

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

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

На практике для создания индекса для некоторой таблицы базы данных пользователь указывает поле таблицы, которое требует индексации.

Термин «индекс» тесно связан с понятием «ключ», хотя между ними есть и некоторое отличие.

Если индексирование организовано на основе ключевого поля, то индекс называется первичным. Ключевые поля, как правило, индексируются автоматически.

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

На практике индексы можно использовать двумя разными способами:

•    последовательного доступа к индексированному файлу, т. е. в последовательности, заданной значениями индексного поля;

•    прямого доступа к отдельным записям индексированного файла на основе заданного значения индексного поля.

Хранимый файл может иметь несколько индексов. Часто индекс создают на основе комбинации двух или более полей. При использовании пары индексов требуется два отдельных просмотра, скорость выполнения за­проса может сильно зависеть от последовательности выполнения отдельных просмотров по индексам.

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

Индекс, в котором не содержатся указатели на все записи индексиро­ванного файла, называется неплотным. Одним из преимуществ неплотных индексов яв­ляется их малый размер по сравнению с плотными индексами. т. к., они содержат меньшее число записей. Это часто позволяет просматривать содержимое БД с большей скоростью, но нельзя выполнить проверку наличия некоторого значения.

 

2.2. Особенности технологии хеширования

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

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

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

Основные особенности технологии хеширования:

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

• для сохранения записи в СУБД сначала вычисляется хеш-адрес новой записи, после чего Диспетчер файлов помещает эту запись по вычисленному адресу;

• для извлечения нужной записи по заданному значению хеш-поля в СУБД сначала вычисляется хеш-адрес, а затем Диспетчеру файлов посылается запрос на извлечение записи по вычисленному адресу.

Технология хеширования имеет свои недостатки.

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

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

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