Индексирование

 

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

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

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

 

 

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

 

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

При двухуровневой схеме ключи (свертки) отделены от содержимого записей – рис. 8.3.

 

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

 

Поскольку основная работа производится с короткими индексными файлами, а не с записями таблиц, двухуровневая схема оказывается производительней.

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