15. Методы поиска в бд

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

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

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

Записи последовательно перебираются, начиная с первой. Для каждой записи значение поля поиска сравнивается со значением ключа поиска. Окончание поиска – по соответствию значения поля искомому значению. Для ускорения поиска можно использовать упорядочивание по частоте выборки записей, что, однако, на практике редко применимо.

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

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

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

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

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

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

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

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

Наиболее распространенный в БД метод поиска. Основывается на использовании индексной организации данных. Требуемая упорядоченность по ключу поиска поддерживается индексом, в котором собственно и проводится поиск. Факторами ускорения поиска являются:

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

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

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

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

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

5. Хэшированный поиск.

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

- преобразование значения ключа в числовое значение (при нечисловом ключе),

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

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

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