Включение в B–дерево

Нужно включить в это дерево элемент с ключом 22.

Включение состоит из этапов:

1. Выяснение, что ключ 22 отсутствует (включение в страницу С невозможна т.к. она уже заполнена).

2. Страница С расщепляется на две страницы, т.е. размещается новая страница D.

3. Количество m + 1 ключей поровну распределяется на C и D, а средний ключ перемещается на один уровень вверх, на страницу предок А.

На рис. 23 изображено B – дерево рис. 22 после включения элемента с ключом 22.

Причина необходимости создания структуры типа Б-дерева заключается в желании избежать обязательного просмотра всего содержимого индексированного файла соглас­но его физической последовательности. Дело в том, что если индексированный файл имеет большой размер, то и его индекс также очень велик. Поэтому последовательный просмотр даже одного только индекса требует больших затрат времени. Разрешить эту проблему можно тем же способом, что и раньше: рассмотреть индексный файл как обычный хранимый файл и создать для него еще один индекс. Эту операцию можно осуществлять повторно нужное количество раз (обычно она применяется трижды, по­скольку создание большого количества иерархических уровней индексирования требует­ся для очень больших файлов). При этом индекс на каждом из уровней будет неплотным по отношению к нижнему индексируемому уровню (он обязательно должен быть не­плотным, иначе такая структура бессмысленна, так как уровень п содержал бы такое же количество записей, что и уровень п+ 1, а для просмотра потребовалось бы такое же дли­тельное время).

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

Индексные Б–деревья. Верхний (первый) уровень индекса делит весь диапазон возможных значений ключа на m крупных интервалов (3).

Каждая ячейка 1–го уровня связана с блоком (страницей) ячеек 2–го уровня индекса.Каждая ячейка каждого блока 2–го уровня связана с блоком ячеек 3–го уровня и т. д.

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

На рис.3 изображено индексное дерево (3 уровня, построенные для упорядоченного основного массива, записи которого имеют диапазон значений ключа от 6 до 99).

Рис. 3. Пример структуры типа Б-дерева

6. Применение бинарных деревьев. Кодирование и сжатие данных. Кодовые деревья, дерево Хаффмена.

1)Бинарные деревья применяются для поиска дубликатов в тексте. Алгоритм: считывается 1-е число и помещается в корень дерева с пустым левым и правым поддеревьями, затем каждое след. Число сравнивается с числом, находящемся в корне. Если значения совпадают, то это дубликат, если новое число меньше значения корня, то процесс повторяется для левого поддерева и т.д Так продолжается пока не встретим дубликат или пока не достигнем пустое дерево.

2)Для сортировки

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

3)задача поиска информации(см.дерево поиска)

4)для представления арифметических выражений

Рассмотрим метод представления выражения,содерж.операнды и операторы в виде строгого бинарного дерева.Корень содержит оператор,кот.может быть применен к результ.выражения, представлен левым и правым поддеревом.Узел представляет оператор имеет 2 непустых поддерева.При этом не требуются (), т.к.структура дерева определяет порядок операций.

5)использование индексных деревьев для индексации массивов(В-деревьев сильноветвящихся)

Нелинейн.структуры индексов ключевых полей и не повторяющихся полей.При организации индексов чаще всего исп.древовид.структуры в виде В-деревьев.Узел такого дерева можно представить в виде:

х_i-i-ое значение индексир.поля

р_i-указатель на вершину содерж.значение индексир поля <или = х_i, р_i+1≥ хi_.

n-порядок В-дерева

Листовая вершина содержит информацию о нахождении стр.в файле базы данных записями имеющ.соответ зн-ия индексир.поля.

6)задача кодирования и сжатия информации(деревья Хаффмена).Для кодирования и декодирования сообщений.

Допустим,что алфавит состоит из 4-х символов.

Сообщение: ABACCDA,закодируем его 010100010000000111010-21 бит

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

Поиск по сайту: