Ключ для таблицы определяется с целью автоматической сортировки записей, контроля отсутствия повторяющихся значений, которые находятся в ключевых полях записей, и ускорения выполнения поисковых операций таблице. В СУБД для выполнения этих функций применяется индексирование.
Термины «индекс» и «ключ» тесно связаны между собой.
Индексом является средство ускорения поиска записей в таблице и других операций, связанных с поиском: модификации, извлечения, сортировки и т.д.
Индексированной называют таблицу, для которой используют индекс.
Индекс выступает в роли оглавления таблицы и просматривается до обращения к записям таблицы. В отдельных системах (к примеру, Paradox) индексы помещаются в индексные файлы, которые сохраняются отдельно от файлов табличных.
Организация физического доступа к данным зависит от:
- типа содержимого поля ключа записей индексного файла;
- вида ссылок, которые используются на запись основной таблицы;
- метода поиска необходимых записей.
Поле ключа индексного файла может содержать свертку ключа (хэш-код) или значения ключевых полей таблицы, которая индексируется. Преимуществом хранения хэш-кода, а не значения, является постоянная и достаточно маленькая длина свертки (например, 4 байта), которая не зависит от длины начального значения ключевого поля. Это достаточно эффективно влияет на скорость выполнения поисковых операций.
Недостаток хеширования – это обязательное выполнение операции свертки, на которую уходит некоторое время, а также возможность возникновения коллизий (при свертке разных значений можно получить одинаковый хэш-код).
При создании ссылки на запись таблицы возможно использование 3 типов адресов: символического (идентификатора), относительного и абсолютного (действительного).
В практической деятельности зачастую используют 2 поисковых метода: бинарный (базируется на делении поискового интервала пополам) и последовательный.
Одноуровневая схема индексирования таблиц
Индексный файл при одноуровневой схеме хранит короткие записи, имеющие 2 поля: поле адреса начала блока и поле содержимого старшего ключа (хэш-кода ключа) данного блока (рисунок 1).
Записи каждого блока располагаются по возрастанию значения ключа или свертки. Ключ последней записи каждого блока является его старшим ключом.
Основной недостаток одноуровневой схемы состоит в хранении ключей (сверток) записей вместе с записями, что приводит к возрастанию поискового времени записей.
Двухуровневая схема индексирования таблиц
Более рациональной является двухуровневая схема, в которой ключи (свертки) записей отделяются от содержимого записей (рисунок 2).
Индекс основной таблицы в данной схеме разнесен по нескольким файлам: один файл главного индекса и множество файлов с блоками ключей.
Виды индексов
При создании индекса для таблицы базы данных пользователем указывается поле таблицы, для которого требуется индексация. Во многих СУБД ключевые поля таблицы обычно индексируются автоматически.
Индексы, которые создаются пользователем для неключевых полей, называются вторичными (или пользовательскими) индексами. Индексные файлы, которые создаются для поддержания вторичных индексов, называют файлами вторичных индексов.
Некоторые СУБД (к примеру, Access), индексы на первичные и вторичные не делят.
Главной причиной увеличения скорости выполнения разных операций в индексированных таблицах является выполнение основной части работы не с таблицами, а с небольшими индексными файлами.
