Часть 2. Индексирование

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

Для реализации этих функций в СУБД применяют индексирование.

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

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

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

 

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

 

В некоторых системах, например, Paradox, индексы хранятся в индексных файлах, хранимых отдельно от таб­личных файлов.

Варианты решения проблемы организации физического доступа к инфор­мации зависят в основном от следующих факторов:

• вида содержимого в поле ключа записей индексного файла;

• типа используемых ссылок (указателей) на запись основной таблицы;

• метода поиска нужных записей.

 

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

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

Недостатком хеширования является необходимость выполнения операции свертки (требует определенного времени), а также борьба с воз­никновением коллизий (свертка различных значений может дать одина­ковый хеш-код).

 

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

 

На практике чаще всего используются два метода поиска: последователь­ный и бинарный (основан на делении интервала поиска пополам).

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

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

 

Рис. 3. Одноуровневая схема индексации

 

 

В каждом блоке записи располагаются в порядке возрастания значения ключа или свертки. Старшим ключом каждого блока является ключ его последней записи.

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

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

2. Поиск в индексном файле записи о блоке, значение первого поля кото­рого больше полученной свертки (это гарантирует нахождение искомой свертки в этом блоке).

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

 

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

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

Рис. 4. Двухуровневая схема индексации

 

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

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

Ин­дексные файлы, создаваемые по ключевым полям таблицы, часто называют­ся файлами первичных индексов.

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

 

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

Связь вторичного индекса с элементами данных базы может быть уста­новлена различными способами. Один из них - использование вторичного индекса как входа для получения первичного ключа, по которому затем с использованием первичного индекса производится поиск необходимых за­писей (рис. 5).

Рис. 5. Способ использования вторичных индексов

 

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

Главная причина повышения скорости выполнения различных операций в индексированных таблицах состоит в том, что основная часть работы про изводится с небольшими индексными файлами, а не с самими таблицами. Наибольший эффект повышения производительности работы с индексиро­ванными таблицами достигается для значительных по объему таблиц.

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