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

Презентация на тему Презентация на тему Сильноветвящиеся Б-деревья, предмет презентации: Информатика. Этот материал содержит 16 слайдов. Красочные слайды и илюстрации помогут Вам заинтересовать свою аудиторию. Для просмотра воспользуйтесь проигрывателем, если материал оказался полезным для Вас - поделитесь им с друзьями с помощью социальных кнопок и добавьте наш сайт презентаций ThePresentation.ru в закладки!

Слайды и текст этой презентации

Слайд 1
Текст слайда:

Сильноветвящиеся Б-деревья

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


Слайд 2
Текст слайда:

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

Пример


Слайд 3
Текст слайда:

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

Пример


Слайд 4
Текст слайда:

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


Слайд 5
Текст слайда:

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


Слайд 6
Текст слайда:

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



Слайд 7
Текст слайда:

 


Слайд 8
Текст слайда:

Б-деревья порядка m

 


Слайд 9
Текст слайда:

 


Слайд 10
Текст слайда:

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

• 10 • 20 •

• 5 • 8 •9 •

• 11 •14 •

• 21• 25 • 30•40 •


Слайд 11
Текст слайда:

 


Слайд 12
Текст слайда:

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

• X •

• X • X •

• X • X •

• X • X •

• X • X •

• X • X •


Слайд 13
Текст слайда:

 


Слайд 14
Текст слайда:

Алгоритм построения Б-дерева порядка m

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


Слайд 15
Текст слайда:

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

• К •

• К • У •

• К • Р • У •

• А • К • Р • У •

• А • К • П • Р • У •

• П •

• А • К •

• Р • У •

• П •

• А • К •

• Р • У •

• А • К • О •

• А • В • К • О •

• А • В • Е • К • О •

• Е • П •

• А • В •

• Р • У •

• К • О •

• Е • П •

• А • В •

• Р • У •

• К • О •

• К • Л • О •

• К • Л • Н • О •

• И • К • Л • Н • О •

• Е • Л • П •

• А • В •

• Р • У •

• И • К •

• Н • О •

• Р • Т • У •


Слайд 16
Текст слайда:

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


Обратная связь

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

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

Это сайт презентаций, докладов, проектов, шаблонов в формате PowerPoint. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами с другими пользователями.


Для правообладателей

Яндекс.Метрика