🗊Презентация Сильноветвящиеся Б-деревья

Сильноветвящиеся Б-деревья Постановка задачи: До сих пор рассматривались только двоичные деревья. Этого во многих случаях вполне достаточно: например, для описания отношений «человек и его родители». Если рассмотреть отношения «человек и его дети», то двоичных деревьев не всегда достаточно, требуются деревья со многими ветвями. Будем называть их сильноветвящимися.

Если задать максимальное количество детей, то можно использовать для их представления массив. Если задать максимальное количество детей, то можно использовать для их представления массив. Но так как количество детей сильно отличается, то это может привести к плохому использованию памяти.

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

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

Если не хватает оперативной памяти, то возможно использовать внешнюю память. Если не хватает оперативной памяти, то возможно использовать внешнюю память. Решение: Вершины дерева разместить во внешней памяти (на диске), а ссылки оставить в оперативной памяти и ссылаться на адреса на диске. Т.к. работа с внешней памятью, то скорость обращения уменьшается и необходимо минимизировать количество обращений к диску. Сильноветвящиеся деревья были идеальным решением, т.к. было предложено при одном обращении к диску считывать не одну вершину, а целую группу.

За одно обращение к диску считывается поддерево, которое будем называть страницей. За одно обращение к диску считывается поддерево, которое будем называть страницей. Размер страницы обычно кратен размеру сектора диска.

Пример. Для n= элементов: Пример. Для n= элементов: если использовать двоичные деревья, то потребуется = 20 шагов поиска; если сильноветвящиеся (S=100), = 3. Однако, если сильноветвящееся дерево растет случайным образом, то в худшем случае может потребоваться шагов поиска. Поэтому необходим алгоритм или правило управления ростом сильноветвящихся деревьев.

Б-деревья порядка m Критерий управления ростом дерева был сформулирован Р. Байером (R. Bayer) в 1970 г. Каждая страница (кроме одной) должна содержать (при заданном постоянном m) от m до 2m элементов. Тогда для дерева с n элементами и мах размером страницы 2m вершин в худшем случае потребуется обращений к диску. Коэффициент использования памяти ≥ 50% , т.к. страница всегда заполнена хотя бы наполовину.

Критерий позволяет просто организовать поиск, включение и удаление элементов. Критерий позволяет просто организовать поиск, включение и удаление элементов. Определение Б-дерева порядка m: В каждой странице хранится к элементов данных … <и к+1 указатель , , … , . Каждый указатель либо равен NULL, либо указывает на вершину (страницу), все элементы которой больше но меньше ()

Для каждой вершины (кроме корня) количество элементов m ≤ k ≤ 2m, Для каждой вершины (кроме корня) количество элементов m ≤ k ≤ 2m, для корня 1 ≤ k ≤ 2m 3. Все листья дерева расположены на одном уровне (важное свойство). Пример: Б-дерево порядка m=2 Root

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

Если на этой странице нет элементов, то по адресу с диска считывается страница следующего уровня. Если на этой странице нет элементов, то по адресу с диска считывается страница следующего уровня. Количество обращений к диску равно высоте Б-дерева, т.е. количеству уровней в нем. Определим наибольшую высоту Б-дерева порядка m:

1+2m = 2(m+1) -1 2-й уровень 1+2m = 2(m+1) -1 2-й уровень 1+2m+2m(m+1) = -1 3-й уровень 2-1 h-й уровень n ≥ n min -1 Высота (количество уровней) Б-дерева порядка m из n элементов: Например, при размере страницы m = 255 по сравнению с обычным двоичным деревом требуется в 8 раз меньше обращений к диску.

Алгоритм построения Б-дерева порядка m Выполняется поиск элемента D (добавляемые данные); Если элемента D нет в дереве, то запоминаем страницу по адресу a и позицию Р, в которой ожидали найти элемент; Вставим элемент в позицию Р+1, количество элементов на странице увеличивается на 1; Если k ≤ 2m, то процесс закончен (было место на странице); Если k > 2m, то происходит переполнение страницы. Создаем новую страницу по адресу b, на которую переносим m правых элементов, средний элемент переносим на родительскую страницу, m левых элементов оставляем на странице по адресу a; Включение элемента в родительскую страницу производится по тому же алгоритму; Если родительской страницы нет, то она создается (корневая) с единственным элементом.

К У Р А П О В Е Л Н И Т

Эта схема сохраняет все характерные свойства Б-деревьев. Эта схема сохраняет все характерные свойства Б-деревьев. Получившиеся две новых страницы содержат ровно по m элементов (кроме корня). Если включение элемента в родительскую страницу ведет к переполнению, то разделение страниц может распространиться до самого корня. В этом случае может увеличиться высота дерева. Таким образом, Б-деревья растут несколько странно: от листьев к корню.