Индексирование. 
Информационные системы в экономике

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

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

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

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

Индексный файл — это хранимый файл особого типа, в котором каждая запись состоит из двух значений: данное и RID-указатель.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• [1] Маклаков С. В. BPwin и Erwin. CASE-средства для разработки информационныхсистем. М.: Диалог-МИФИ, 2000.
• [2] Маклаков С. В. BPwin и Erwin. CASE-средства для разработки информационныхсистем. М.: Диалог-МИФИ, 2000.