Поиск информации в бд с использованием структуры типа «бинарное дерево».
В задачах поиска предполагается, что все данные хранятся в памяти с определенной идентификацией и, говоря о доступе, имеют в виду, доступ к ключам, однозначно идентифицирующим связанные с ними совокупности данных. Существуют 2 класса методов, реализующих доступ к данным по ключу: методы поиска по дереву и методы хеширования.
Деревом называется конечное множество, состоящее из одного или более элементов, называемых узлами, таких, что:
Между узлами имеет место отношение типа "исходный-порожденный";
Есть только один узел, не имеющий исходного. Он называется корнем;
Все узлы за исключением корня имеют только один исходный; каждый узел может иметь несколько порожденных;
Отношение "исходный-порожденный" действует только в одном направлении, т.е. ни один потомок некоторого узла не может стать для него предком.
Число порожденных отдельного узла (число поддеревьев данного корня) называется его степенью. Узел с нулевой степенью называют листом или концевым узлом. Максимальное значение степени всех узлов данного дерева называется степенью дерева.
Если в дереве между порожденными узлами, имеющими общий исходный, считается существенным их порядок, то дерево называется упорядоченным. В задачах поиска почти всегда рассматриваются упорядоченные деревья.
Упорядоченное дерево, степень которого не больше 2 называется бинарным деревом. Бинарное дерево особенно часто используется при поиске в оперативной памяти. Алгоритм поиска: вначале аргумент поиска сравнивается с ключом, находящимся в корне. Если аргумент совпадает с ключом, поиск закончен, если же не совпадает, то в случае, когда аргумент оказывается меньше ключа, поиск продолжается в левом поддереве, а в случае когда больше ключа - в правом поддереве. Увеличив уровень на 1 повторяют сравнение, считая текущий узел корнем.
Пример
Дан список студентов, содержащий их фамилии и средний бал успеваемости. В качестве ключа используется фамилия. Предположим, что все записи имеют фиксированную длину, тогда в качестве указателя можно использовать номер записи. Смещение записи в файле в этом случае будет вычислятся как ([номер_записи] -1) * [длина_записи].
Пусть аргумент поиска = "Петров". На рисунке показан один из возможных для этого набора данных бинарных деревьев поиска и путь поиска.
Поиск по бинарному дереву:
Здесь используется следующее правило сравнения строк: значение символа соответствует его порядковому номеру в алфавите. Поэтому "И" меньше "К", а "К" меньше "С". Если текущие символы в сравниваемых строках совпадают, то сравниваются символы в следующих позициях.
Бинарные деревья особенно эффективны в случае когда множество ключей заранее неизвестно, либо когда это множество интенсивно изменяется.
Поиск информации в бд с использованием структуры типа «сильно ветвящееся дерево».
При поиске данных во внешней памяти очень важной является проблема сокращения числа перемещений данных из внешней памяти в оперативную. Поэтому, в данном случае по сравнению с бинарными деревьями более выгодными окажутся сильно ветвящиеся деревья - т.к. их высота меньше, то при поиске потребуется меньше обращений к внешней памяти. Наибольшее применение в этом случае получили В-деревья (В - balanced)
Определение: В-деревом порядка n называется сильно ветвящееся дерево степени 2n+1, обладающее следующими свойствами:
Каждый узел, за исключением корня, содержит не менее n и не более 2n ключей.
Корень содержит не менее одного и не более 2n ключей.
Все листья расположены на одном уровне.
Каждый нелистовой узел содержит два списка: упорядоченный по возрастанию значений список ключей и соответсвующий ему список указателей (для листовых узлов список указателей отсутствует).
Для такого дерева:
сравнительно просто может быть организован последовательный доступ, т.к. все листья расположены на одном уровне;
при добавлении и изменении ключей все изменения ограничиваются, как правило, одним узлом.
В-дерево, в котором истинные значения содержатся только в листьях (концевых узлах), называется В+-деревом. Во внутренних узлах такого дерева содержатся ключи-разделители, задающие диапазон изменения ключей для поддеревьев. Следует отметить, что B-деревья наилучшим образом подходят только для организации доступа к достаточно простым (одномерным) структурам данных.