10. Поиск информации в бд с использованием структуры типа «бинарное дерево».

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

Бинарное дерево поиска (binary search tree, BST) — это бинарное дерево, для которого выполняются дополнительные условия:

• Оба поддерева — левое и правое, являются двоичными деревьями поиска.

• У всех узлов левого поддерева произвольного узла X значения ключей данных меньше, нежели значение ключа данных узла X.

• У всех узлов правого поддерева произвольного узла X значения ключей данных больше, нежели значение ключа данных узла X.

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

Пример:

Таблица 2 Таблица учеников , где № - ключевое поле

№	Фамилия	Имя	Класс	№	Фамилия	Имя	Класс
1	Попов	Егор	2 класс	8	Попов	Мужик	2 класс
2	Омельченко	Сева	4 класс	9	Веселовский	Ян	4 класс
3	Бабаев	Слава	5 класс	10	Бабаев	Слава	5 класс
4	Олегов	Олег	7 класс	11	Матвеев	Слава	7 класс
5	Самойлов	Ян	1 класс	12	Омельченко	Сева	2 класс
6	Самойлов	Стас	3 класс	13	Матвеев	Мужик	4 класс
7	Калинина	Натали	2 класс				7 класс

Рисунок 1 Двоичное дерево поиска для таблицы учеников

11. Поиск информации в бд с использованием структуры типа «сильно ветвящееся дерево».

Сильно ветвящееся деревья могут содержать более чем один ключ в своих узлах.

Сильно ветвящееся дерево - выровненное m-арное дерево поиска, у которого каждая вершина имеет не более 2m и не менее (кроме корня и листов) m потомков и корень, если он не является листом, имеет не менее двух потомков.

Рисунок 2 пример ветвящегося дерева как B-дерево.

Свойства:

• кажд. узел, за искл-ем корня содержит не < n и не > 2n ключей;

• корень содержит не < 1 и не > 2n ключей;

• все листья располологаются на 1 ур-не;

• каждый нелистовой узел содержит 2 списка: упорядоченный по возрастанию список ключей и соответствующий ему список указателей на поддеревья.

• лист-е узлы содержатт т.ж. 2 сп.: 1-й т.ж. и сп-к указ-ей на конкр-е д-е.

12. Методы хеширования для реализации доступа к данным по ключу.

Этот метод используется тогда, когда все множество ключей заранее известно и на время обработки может быть размещено в оперативной памяти. В этом случае строится специальная функция, однозначно отображающая множество ключей на множество указателей, называемая хеш-функцией (от английского "to hash" - резать, измельчать). Имея такую функцию можно вычислить адрес записи в файле по заданному ключу поиска. В общем случае ключевые данные, используемые для определения адреса записи организуются в виде таблицы, называемой хеш-таблицей.

Зачастую Хеш-таблицы помещаются в файлы, которые называют индексными.

Хеширование – один из наиболее быстрых методов доступа к данным, однако он имеет недостатки.

Основные методы хеширования:

• Открытая адресация

• Несвязанная область переполнения

• Связанная область переполнения

• Динамическое хеширование

Недостатки хеширования:

1.   Страницы с записями во внешней памяти могут располагаться неравномерно, с различным количеством пустых страниц между ними.

2.   Возможно совпадение рассчитанных адресов страниц для двух или нескольких записей – коллизия. Значения данных, для которых получены одинаковые адреса –синонимы.

Существует много стратегий разрешения коллизий, но основные из них две:

а

См выше

) с областью переполнения;

б) свободного замещения.