2. Блочный поиск.

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

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

3. Бинарный поиск

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

Если записи имеют фиксированную длину, то смещаемся на нужную запись, если длина записей нефиксированная, то смотрим по меткам, то есть обращаемся в середину памяти и смещаемся далее до первой встретившейся метки.

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

4. Индексный поиск

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

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

Факторами ускорения поиска являются:

- меньшее число проверок при выполнении поиска за счет упорядоченности данных в индексе;

- быстрая выборка проверяемой позиции индекса за счет небольшого объема индекса и выравненности размеров позиций;

- отсутствие необходимости расчета проверяемого значения для записей, т.к. в индексе хранятся уже рассчитанные значения.

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

Существует множество индексных методов доступа. Внутренняя организация индекса может основываться на последовательной или списковой организации данных. Простейшей и сравнительно малоэффективной является последовательная организация. В этом случае в индексе хранятся упорядоченные по значению ключа пары «значение ключа – указатель на запись».

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

При списковой организации индекса он строится в виде дерева. В основном используются два вида деревьев: бинарные и В-деревья. Узел бинарного дерева содержит одно значение ключа и две ссылки на подчиненные узлы: левую – на код дерева с меньшими значениями ключа, правую – на код дерева с большими значениями.

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

Например, заполнение дерева следующими значениями записей: 12, 35, 40, 100, 1, 2, 83, 5, 10, получим дерево, имеющее некоторые очень большие ветви, в то время как другие могут отсутствовать.

Реализация бинарного дерева позволяет сократить время поиска данных по сравнению с бинарным поиском, однако возрастает требуемый объем внешней памяти.

Более сложные в организации В-деревья обеспечивают малую глубину дерева за счет размещения оптимального числа ключей и ссылок в узлах и сбалансированность ветвей за счет специальных алгоритмов построения дерева.

а) Неплотный индекс

Пусть основной файл F упорядочен по полю ключа К. Построим дополнительный файл FD по следующему правилу:

1) записи файла FD имеют формат FD(K, Р), где К – поле, принимающее значение ключа первой записи блока основного файла F; Р – указатель на этот блок;

2) записи файла FD упорядочены по полю К.

Полученный файл FD называется неплотным индексом. Количество записей файла FD равно количеству блоков основного файла F. Для организации файла FD требуется дополнительная внешняя память.

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

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

Полученная структура называется В-деревом порядка т, где т – количество записей в блоке индекса. Такое дерево должно иметь в каждом узле не менее т/2 зависимых узлов и все листья должны располагаться на одном уровне.

Для осуществления последовательного поиска блоки первого уровня могут быть связаны в цепь по возрастанию значения ключа. Поиск в В-дереве выполняется так же, как и в неплотном индексе. Удачный и неудачный поиск записи в В-дереве требует h обменов, где h – число уровней В-дерева.

При поиске по интервалу значений а ≤ К ≤ b вначале выполняется поиск по К = а в В-дереве, а затем – последовательный поиск по условию К ≤ b в блоках 1-го уровня В-дерева.

б) Плотный индекс

Пусть по каким-либо причинам невозможно упорядочить основной файл F по ключу К. Построим дополнительный файл FD по правилу:

1) записи файла FD имеют формат FD(K, Р), где К – поле, принимающее значение ключа записи основного файла F; Р – указатель на эту запись;

2) записи файла FD упорядочены по полю К.

Полученный файл называется плотным индексом. Он строится почти так же, как и неплотный индекс. Различие заключается в том, что для каждого значения ключа К в файле FD имеется отдельная запись, а в неполном индексе - только для значения ключа первой записи блока.

Над плотным индексом можно также построить В-дерево.