Индексно-последовательный способ

Линейный список упорядочивается по первичному ключу. Аналогично блочному методу доступа, он делится на виртуальные блоки размером √N. Затем ключевые поля последних элементов блоков вместе с порядковыми номерами этих элементов в списке включаются в дополнительные списки, которые называются индексами. Таким образом, для списка из таблицы 5 (далее – основного списка):

Таблица 5

будет построен индекс, представленный в таблице 6:

Таблица 6

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

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

Пример 7.Пусть в основном списке таблицы 5 надо просмотреть адрес студента по фамилии Скворцов, т.е. q^{просмотр} = (Фамилия= Скворцов, Домашний адрес), где К_доступ = Скворцов. Задача решается следующим образом:

1. выбирается первый элемент в индексе;

2. его ключевое поле сравнивается с искомым: Соколов = Скворцов;

3. поскольку условие не выполняется, проверяется, возможно ли нахождение искомого элемента в текущем, первом, блоке. Для этого проверяется условие: Соколов > Скворцов;

4. условие выполняется, поэтому из соседнего поля индекса выбирается ссылка на последний элемент первого блока в основном списке – это 2;

5. по этому номеру выполняется обращение к предыдущему, т.е. первому, элементу основного списка;

6. ключевое поле этого элемента сравнивается с искомым ключом: Скворцов = Скворцов;

7. поскольку ключевые поля равны, выводится адрес: пр. Мира, 45 – 3; алгоритм заканчивает работу.

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