Индексирование данных. Индексированные файлы

Определим индексирование как способ доступа к данным в реляци-онной таблице с помощью специальной структуры – индекса.

Индекс – это структура, которая определяет соответствие значения ключа записи (атрибута или группы атрибутов) и местоположения этой записи – КБД (рис. 4.3). Каждый индекс связан с определённой таблицей, но является внешним по отношению к таблице и обычно хранится отдельно от неё.

Индекс
Значение атрибута КБД
Белова FA:00
Волков F6:1E
Волкова F6:00
Осипов FA:2B
Поспелов F6:31
Фридман FA:1D

 

Пространство памяти
F6:00 Волкова ...
F6:1E Волков ...
F6:31 Поспелов ...

 

...
FA:00 Белова ...  
FA:1D Фридман ...  
FA:2B Осипов ...  

 

   

Рис. 4.3. Пример индекса

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

Индексирование используется для ускорения доступа к записям по значению ключа и не влияет на размещение данных этой таблицы. Ускорение поиска данных через индекс обеспечивается за счёт:

  1. упорядочивания значений индексируемого атрибута. Это позволяет про-сматривать в среднем половину индекса при линейном поиске;
  2. индекс занимает меньше страниц памяти, чем сама таблица, поэтому система тратит меньше времени на чтение индекса, чем на чтение таблицы.

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

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

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

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

Для каждой таблицы можно одновременно иметь несколько первичных и вторичных индексов, что также относится к достоинствам индексирования.

Различают индексы по одному полю и по нескольким (составные). Составной индекс включает два или более столбца одной таблицы (рис. 4.4). Последовательность вхождения столбцов в индекс определяется при его создании. Из примера на рис. 4.4 видно, что данные в индексе отсортированы по первому столбцу (ID), внутри группы с одинаковыми значениями ID – отсортированы по второму столбцу (EDATE), а внутри группы с одинаковыми значениями ID и EDATE – по третьему столбцу (CODE).

Таблица
ID EDATE CODE FIRM PRICE
01.12.95 A4 Комус 312.0
01.12.95 A4 Партия 321.5
02.12.95 А2 ОАО "Заря" 110.6
10.12.95 А4 Фирма "Б+" 314.0
01.12.95 А2 Партия 114.0
01.12.95 А1 Amos ltd. 52.8

 

Индекс
ID EDATE CODE
01.12.95 A4
02.12.95 A2
10.12.95 A4
01.12.95 A2
01.12.95 A4
02.12.95 A1

 

Рис. 4.4. Пример составного индекса