3.3. Методы поиска и индексирования данных

При рассмотрении последующего учебного материала используются модели, приведенные в разд.3.1, 3.2.

3.3.1. Последовательный поиск

Последовательный поиск заключается в последовательной проверке всех записей файла на их соответствие условию поиска Q [17]. Записи, значения полей которых удовлетворяют условию Q, выдаются в качестве результата поиска.

Рис. 3.7. Пример организации файла при начальной загрузке

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

Если ключ К с равной вероятностью может принимать любое из заданных значений, то в среднем для выполнения поиска требуется время

Поиск по интервалу значений ключа а ≤ К ≤ b. Алгоритм поиска заключается в последовательном просмотре всех записей файла, так как зарание неизвестно, какие записи удовлетворяют условию Q, а какие не удовлетворяют.

Требуемое время на поиск

Поиск по множеству значений K = ai, i = 1, 2, ..., п, где ai принимает значения из множества {а1, а2, ..., аi, ..., ап}. Алгоритм поиска заключается в последовательном просмотре всех записей файла, при чем для каждой записи осуществляется п проверок по равенству: К = аi, где i = 1, 2, ..., п.

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

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

78

Записи в файле можно упорядочить, например, по возрастанию или убыванию значения первичного ключа соответственно:

В этом случае можно построить более эффективные алгоритмы поиска, поскольку после сравнения значения а (условие поиска Q: К = а) со значением ключа i-й записи файла ясно, в какой части файла продолжать поиск [17].

Методы поиска записей в упорядоченном файле различаются друг от друга стратегией выбора очередной записи из фала для выполнения операции сравнения ключа в соответствии с заданным условием Q. Метод бинарного поиска основан на делении интервала поиска пополам.

Поиск по равенству К = а. Алгоритм поиска заключается в следующем. Файл считают

упорядоченным по возрастанию ключа. Сравнивают значения ключа средней записи Ki, где i = é nз.ф./2ù со значением а. Если К = а то поиск удачный и алгоритм заканчивает свою работу. Если Кi < а, то для продолжения поиска выбирается средняя запись правой половины файла: зi, ..., зj, ..., зпз., где

Если Кi > а, то для продолжения поиска выбирается средняя запись левой половины файла: з1, з2, ...,

зj, ..., зi, где

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

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

Поиск по интервалу значений а ≤ К ≤ b. Алгоритм поиска следующий. Вначале выполняется бинарный поиск записи, значение ключа которой удовлетворяет условию Кi = а, либо, если такой записи нет в файле, то значение ключа которой является наиболее близким к а по условию а ≤ Кi. Далее последовательно читаются записи в блоках файла до тех пор, пока не будет нарушено условие: Кi ≤ b.

3.3.3. Индекс - «бинарное дерево»

Любой бинарный алгоритм поиска в упорядоченном файле БД можно представить с помощью соответствующего бинарного дерева [17]. Это бинарное дерево можно реализовать в виде самостоятельного файла (или индекса). При этом операции поиска будут освобождены от необходимости каждый раз вычислять адреса записей (они будут сформированы один раз при начальной загрузке файла БД и при последующих добавлениях в файл новых записей).

На рис. 3.8 представлено бинарное дерево, построенное для файла из 15 записей [17]. Запись бинарного дерева состоит из поля ключа записи и двух полей указателей. Один указатель для левого поддерева, другой – для правого поддерева. Листовые записи бинарного дерева содержат указатели на блоки файла основных записей (файла данных). Для уменьшения количества операций обмена с внешней памятью при выполнении поиска соседние записи в бинарном дереве объединяются в блоки. На слайде объединяемые в один блок записи бинарного дерева очерчены штриховой линией.

Записи бинарного дерева обычно меньше по объему памяти записей основного файла Vз.б.д. < Vз., так как содержат только одно поле данных (поле ключа) и два служебных поля для хранения индексов, то

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

79

Рис. 3.8. Пример бинарного дерева

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

3.3.4. Неплотный индекс

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

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

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

Рис. 3.9. Пример неплотного индекса

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

80

память.

Рис. 3.10. Пример структуры типа В-дерево

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

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

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

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

При поиске по интервалу значений а ≤ К ≤ b вначале выполняется поиск по К = а в В-дереве, а затем

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

3.3.5.Плотный индекс

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

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

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

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

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

81