Методы поиска информации в базе данных

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

1. Последовательная обработка области БД. Областью БД может быть файл, часть файла, несколько файлов или другое множество блоков. Обычно области присваивается имя, ее физические границы задаются при описании БД. Последовательная обработка предполагает выборку записей из области БД независимо от структурных связей (ассоциаций), в которых участвуют записи. Система последовательно перебирает блоки области, пропускает свободные участки и выдает пользователю записи БД в физической последовательности их хранения. Если записи в БД отсортированы, то поиск продолжается до тех пор, пока значение ключа записи не станет больше заданного. Разновидностью последовательного поиска отсортированной БД является блочный поиск: вначале отыскивается нужный блок (совокупность записей), а затем уже нужная запись внутри блока.

Если условие поиска задано равенством К=а, где К - значение ключевого поля, то в среднем для выполнения поиска потребуется время

t_п = t₀[n_блф/2],

где nблф - количество блоков в файле данных. Если поиск осуществляется по интервалу значений ключа a < k < b, то tп = t0 nблф .

При поиске по множеству значений К=ai; ai Î{a1, a2,...,an}, i=1,n; для каждой записи осуществляется n проверок по равенству k=ai.

Тогда

t_п » t₀ n_блф + t_c n n_зф/2

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

2. Доступ по ключу БД. Ключ базы данных присваивается для каждой записи системой и определяет расположение записи в памяти ЭВМ. Зная ключ, СУБД может наиболее быстро извлечь требуемую запись.

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