Индексно-произвольный способ

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

В таком случае список упорядочивается по тому ключу, по которому предполагаются наиболее частые запросы. По этому ключу организуется индексно-последовательный доступ (см. предыдущий раздел). Остальные значения первичных ключей формируют дополнительный список – индекс. Они включаются в индекс в полном составе из исходного списка и упорядочиваются. Кроме того, в индекс записываются ссылки на эти элементы в основном списке.

Пример 8. Организуем индексно-произвольный доступ к линейному списку из таблицы 5, обеспечив индексно-последовательный доступ по ключу Фамилия.

Тогда построим дополнительный индекс, показанный в таблице 7:

               

       Таблица 7

№ п/п	Номер зачетной книжки	Ссылка
1	01278	2
2	02343	3
3	02347	4
4	02544	1

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

Таким образом,  решение задачи включает три линейных списка, представленные в таблицах 5, 6, 7. 

Размещение элементов в упорядоченном списке

Для размещения элемента с ключом К_доступ в упорядоченном списке возможны два подхода:

1. включение элемента в список с переупорядочением списка;

1. использование областей переполнения.

Первый подход показан ниже:

1. пусть исходный список соответствует таблице 8:

                                                                Таблица 8

№ п/п	Фамилия	Имя	Отчество	Номер зачетной книжки	Домашний адрес
1	Скворцов	Олег	Иванович	02544	пр. Мира, 45 - 3
2	Соколов	Юрий	Кузьмич	01278	ул. Леонова, 23 - 98
3	Строков	Иван	Иванович	02343	ул. Красная, 9 - 2
4	Супруненко	Виктор	Егорович	02347	Каштановая аллея, 23 - 5

1. добавляется элемент со структурой таблицы 9, т.е. q^{добавление} = (Фамилия = Стручков, Имя = Петр, Отчество = Кузьмич, Номер зачетной книжки = 18345, Домашний адрес = ул. Леонова, 14-16):

                                                       Таблица 9

Фамилия	Имя	Отчество	Номер зачетной книжки	Домашний адрес
Стручков	Петр	Кузьмич	18345	ул. Леонова, 14 - 16

3)        результирующий список соответствует таблице 10 (добавленный элемент выделен заливкой):

                                                               Таблица 10

№ п/п	Фамилия	Имя	Отчество	Номер зачетной книжки	Домашний адрес
1	Скворцов	Олег	Иванович	02544	пр. Мира, 45 - 3
2	Соколов	Юрий	Кузьмич	01278	ул. Леонова, 23 - 98
3	Строков	Иван	Иванович	02343	ул. Красная, 9 - 2
4	Стручков	Петр	Кузьмич	18345	ул. Леонова, 14 - 16
5	Супруненко	Виктор	Егорович	02347	Каштановая аллея, 23 - 5

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

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

Иллюстрация этого подхода показана ниже: