Поиск данных по вторичным ключам

2.3.4. Поиск по вторичным ключам
До сих пор рассматривались способы поиска в таблице по ключам, позволяющим однозначно идентифицировать запись. Такие ключи называются и е р в и ч н ы м и Возможен вариант организации таблицы, при котором отдельный ключ не позволяет однозначно идентифицировать запись. Такая ситуация часто встречается в базах данных. Идентификация записи осуществляется по некоторой совокупности ключей. Ключи, не позволяющие однозначно идентифицировать запись в таблице, называются в т о р и ч н ы м и ключами.
Даже при наличии первичного ключа, для поиска записи могут быть использованы вторичные. Например, поисковые системы InterNet часто организованы как наборы записей, соответствующих Web-страницам. В качестве вторичных ключей для поиска выступают ключевые слова страниц, а сама задача поиска сводится к выборке из таблицы некоторого множества записей, содержащих требуемые вторичные ключи.
2.3.3.1. Инвертированные иноексы
Рассмотрим метод организации таблицы с инвертированными индексами (рис. 30). Для таблицы строится отдельный набор данных, содержащий так называемые и н в е р т и р о в а н н ы е индексы. Вспомогательный набор содержит для каждого значения вторичного ключа отсортированный список адресов записей таблицы, которые содержат данный ключ.
Поиск осуществляется по вспомогательной структуре достаточно быстро, так как фактически отсутствует необходимость обращения к основной структуре данных. Область памяти, используемая для индексов, является относительно небольшой по сравнению с другими методами организации таблиц.
Недостатками данной системы являются большие затраты времени на составление вспомогательной структуры данных и ее обновление. Причем эти затраты возрастают с увеличение объема базы данных.
Система инвертированных индексов является чрезвычайно удобной и эффективной при организации поиска в больших таблицах.
2.3.3.2. Битовые карты
Для таблиц небольшого объема используют организацию вспомогательной структуры данных в виде битовых карт (рис. 31). Для каждого значения вторичного ключа записей основного набора данных записывается последовательность битов. Длина последовательности битов равна числу записей. Каждый бит в битовой карте соответствует одному значению вторичного ключа и одной записи. Единица означает наличие ключа в записи, а нуль - отсутствие.
Основным преимуществом такой организации является очень простая и эффективная организация обработки сложных запросов, которые могут объединять значения ключей различными логическими предика-тами. В этом случае поиск сводится к выполнению логических операций запроса непосредственно над битовыми строками и интерпретации результирующей битовой строки. Другим преимуществом является простота обновления карты при добавлении записей.
К недостаткам битовых карт следует отнести увеличение длины строки карты пропорционально длине таблицы. При этом заполненность карты единицами уменьшается с увеличением длины файла. Для таблицы большой длины и редко встречающихся ключей битовая карта превращается в большую разреженную матрицу, состоящую в основном из одних нулей.

28. Упорядоченные деревья поиска. Способы реализации и основные операции

Обычные деревья не дают выигрыша при хранении множества значений. При поиске элемента все равно необходимо просмотреть все дерево. Однако можно организовать хранение элементов в дереве так, чтобы при поиске элемента достаточно было просмотреть лишь часть дерева. Для этого надо ввести следующее требование упорядоченности дерева.
Двоичное дерево упорядочено, если для любой вершины х справедливо такое свойство: все элементы, хранимые в левом поддереве, меньше элемента, хранимого в х, а все элементы, хранимые в правом поддереве, больше элемента, хранимого в х.
Важное свойство упорядоченного дерева: все элементы его различны. Если в дереве встречаются одинаковые элементы, то такое дерево является частично упорядоченным.
В дальнейшем будет идти речь только о двоичных упорядоченных деревьях, опуская слово «упорядоченный».
Итак, основными операциями, производимыми с упорядоченным деревом, являются:
поиск вершины;
добавление вершины;
удаление вершины;
очистка дерева.
Реализацию этих операций приведем в виде соответствующих процедур.
Алгоритмы поиска можно записать в рекурсивном виде. Если искомое значение Item меньше Tree" Data, то поиск продолжается в левом поддереве, если равен - поиск считается успешным, если больше - поиск продолжается в правом поддереве; поиск считается неудачным, если достигли пустого поддерева, а элемент найден не был.

Случайные деревья поиска и оптимальные деревья поиска. Основные понятия

Случайные деревья поиска представляют собой упорядоченные бинарные деревья поиска, при создании которых элементы (их ключи) вставляются в случайном порядке.
При создании таких деревьев используется тот же алгоритм, что и при добавлении вершины в бинарное дерево поиска. Будет ли созданное дерево случайным или нет, зависит от того, в каком порядке поступают элементы для добавления. Примеры различных деревьев, создаваемых при различном порядке поступления элементов, приведены ниже.
При поступлении элементов в случайном порядке получаем дерево с минимальной высотой h (рис. 32, а), а соответственно минимизируется время поиска элемента в таком дереве, которое пропорционально O(log n). При поступлении элементов в упорядоченном виде (рис. 32, 6) или в несколько необычном порядке (рис. 32, в) происходит построение вырожденных деревьев поиска (оно вырождено в линейный список), что нисколько не сокращает время поиска, которое составляет O(n).
2.3.4.3. Оптимальные деревья поиска
В двоичном дереве поиск одних элементов может происходить чаще, чем других, т. е. существуют вероятности рА поиска А..-го элемента и для различных элементов эти вероятности неодинаковы. Можно сразу предположить, что поиск в дереве в среднем будет более быстрым, если те элементы, которые ищут чаще, будут находиться ближе к корню дерева.
Пусть даны 2п+1 вероятностей р1, р2, р„, q< q> q где р,.- вероятность того, что аргументом поиска является К,.; q,. - вероятность того, что аргумент поиска лежит между К,. и К,. ~, q< - вероятность того, что аргумент поиска меньше, чем К,; q„- вероятность того, что аргумент поиска больше, чем К„.
г
Дерево поиска называется оптимальным, если его цена минимальна или, другими словами, оптимальное бинарное дерево поиска - это бинарное дерево поиска, построенное в расчете на обеспечение максимальной производительности при заданном распределении вероятностей поиска требуемых данных.
Существует подход построения оптимальных деревьев поиска, при котором элементы вставляются в порядке уменьшения частот, что дает в среднем неплохие деревья поиска. Однако этот подход может дать вырожденное дерево поиска (см. 2.3.4.2), которое будет далеко от оптимального.
Еще один подход состоит в выборе корня 1 таким образом, чтобы максимальная сумма вероятностей для вершин левого поддерева или правого поддерева была настолько мала, насколько это возможно. Такой подход также может оказаться плохим в случае выбора в качестве корня элемента с малым значением рА.
30. Сбалансированные по высоте деревья поиска. Способы реализации и основные операции

Как уже говорилось ранее (см. 2.3.4.2), в худшем случае (дерево вырождено в линейный список) хранение данных в упорядоченном бинарном дереве никакого выигрыша в сложности операций (поиск/добавление/удаление) по сравнению с массивом или линейным списком не дает. В лучшем случае (дерево сбалансировано) для всех операций получается логарифмическая сложность, что гораздо лучше.
Идеально сСбалансированным называется дерево, у которого для каждой вершины выполняется требование: число вершин в левом и правом поддеревьях различается не более чем на 1. Однако идеальную сбалансированность довольно трудно поддерживать. В некоторых случаях при добавлении/удалении может потребоваться значительная перестройка дерева, не гарантирующая логарифмической сложности. Поэтому в 1962 году два советских математика Г М. Адельсон-Вельский и Е. М. Ландис ввели менее строгое определение сбалансированности и доказали, что при таком определении можно написать программы добавления/ удаления, имеющие логарифмическую сложность и сохраняющие дерево сбалансированным.
Дерево считается сбалансированным по АВЛ (в дальнейшем просто «сбалансированным»), если для каждой вершины выполняется требование: высота левого и правого поддеревьев различаются не более, чем на 1. Не всякое сбалансированное дерево идеально сбалансировано, но всякое идеально сбалансированное дерево сбалансировано.
При операциях добавления и удаления может произойти нарушение сбалансированности дерева. В этом случае потребуются некоторые преобразования, не нарушающие упорядоченности дерева и способствующие лучшей сбалансированности.