Двоичный способ

Элементы линейного списка упорядочены по первичному ключу. Список последовательно делится на части, уменьшая пространство поиска каждый раз вдвое.

Рассмотрим вначале, как выполняется просмотр полей элемента.

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

1. список виртуально делится пополам: «средним» элементом оказывается элемент, имеющий ключ Соколов;

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

1. поскольку ключи не равны, определяется, в какой из полученных двух половин списка продолжать поиск. Для этого проверяется условие: Соколов  < Скворцов;

1. условие выполняется, поэтому поиск продолжается в первой половине, т.е. исходный список уменьшился до размеров таблицы 4:

   

                                                       Таблица 4

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

1. этот новый список делится на две части: «средним» элементом оказывается элемент, имеющий ключ Скворцов;

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

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

Пример 6. Пусть надо просмотреть адрес студента по фамилии Сидоров, т.е. q^{просмотр} = (Фамилия = Сидоров, Домашний адрес), где К_доступ = Сидоров.

Первые пять шагов решения задачи совпадают с предыдущим примером. Затем выполняются следующие шаги:

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

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

1. условие выполняется, поэтому делается попытка продолжить поиск в «верхней» части списка. Однако элемент с ключом К_э = Скворцов является единственным элементом в этой части, поэтому выдается диагностическое сообщение об отсутствии искомого элемента в списке; алгоритм заканчивает работу.

Задача добавления нового элемента решается аналогично способу, рассмотренному ранее для упорядоченного списка.

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

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

                                                               

                                                       Таблица 5

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

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

               

                    Таблица 6

№ п/п	Фамилия	№ п/п в основном списке
1	Соколов	2
2	Супруненко	4

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

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

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

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

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

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

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

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

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

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

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