Индексирование данных. 
виды индексов. 
составные и многоуровневые индексы

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

Значения индексируемого атрибута упорядочиваются (чаще всего, по возрастанию). Индекс обычно хранится в отдельном файле или отдельной области памяти. Пустые значения атрибутов (null) не индексируются.

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

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

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

Различают одиночные индексы и составные. Составной индекс включает два или более столбца одной таблицы (рис. 1). Последовательность вхождения столбцов в индекс определяется при создании индекса.

Таблица.

Индекс.