🗊Презентация B-деревья

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
B-деревья, слайд №1B-деревья, слайд №2B-деревья, слайд №3B-деревья, слайд №4B-деревья, слайд №5B-деревья, слайд №6B-деревья, слайд №7B-деревья, слайд №8B-деревья, слайд №9B-деревья, слайд №10B-деревья, слайд №11B-деревья, слайд №12B-деревья, слайд №13B-деревья, слайд №14B-деревья, слайд №15B-деревья, слайд №16B-деревья, слайд №17B-деревья, слайд №18B-деревья, слайд №19B-деревья, слайд №20B-деревья, слайд №21
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему B-деревья. Доклад-сообщение содержит 21 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

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

Слайд 1


B-деревья
Описание слайда:
B-деревья

Слайд 2


Определение В-дерево изобретено в 1972г. Р.Байером и Е. Маккрайтом Предназначено для создания мелких деревьев для быстрого доступа к диску Мелкие деревья имеют мало уровней; продвинуться к цели по такому дереву можно, выполнив небольшое количество проходов. В-деревья — это мощное решение проблемы дискового хранения; фактически каждая коммерческая система баз данных уже давно использует вариации В-деревьев
Описание слайда:
Определение В-дерево изобретено в 1972г. Р.Байером и Е. Маккрайтом Предназначено для создания мелких деревьев для быстрого доступа к диску Мелкие деревья имеют мало уровней; продвинуться к цели по такому дереву можно, выполнив небольшое количество проходов. В-деревья — это мощное решение проблемы дискового хранения; фактически каждая коммерческая система баз данных уже давно использует вариации В-деревьев

Слайд 3


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

Слайд 4


Определение Страница называется узловой, если индекс страницы указывает на другую страницу Страница называется листовой если индекс указывает на данные, (от слова "листва"). Максимальное количество индексов на странице называется порядком страницы
Описание слайда:
Определение Страница называется узловой, если индекс страницы указывает на другую страницу Страница называется листовой если индекс указывает на данные, (от слова "листва"). Максимальное количество индексов на странице называется порядком страницы

Слайд 5


Определение Каждая страница максимально может иметь количество дочерних страниц, равное ее порядку. Для В-деревьев существует правило: ни одна из страниц, кроме верхней и листовых, не может иметь индексов, количество которых меньше половины порядка (order/2). листовая страница может иметь меньшее количество индексов(order/2 -1)
Описание слайда:
Определение Каждая страница максимально может иметь количество дочерних страниц, равное ее порядку. Для В-деревьев существует правило: ни одна из страниц, кроме верхней и листовых, не может иметь индексов, количество которых меньше половины порядка (order/2). листовая страница может иметь меньшее количество индексов(order/2 -1)

Слайд 6


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

Слайд 7


Построение В-дерева: 1. 6 11 3 12 14 2 10 5 4 7 8 13 1 9
Описание слайда:
Построение В-дерева: 1. 6 11 3 12 14 2 10 5 4 7 8 13 1 9

Слайд 8


Построение В-дерева: 2-3. 6 11 3 12 14 2 10 5 4 7 8 13 1 9
Описание слайда:
Построение В-дерева: 2-3. 6 11 3 12 14 2 10 5 4 7 8 13 1 9

Слайд 9


Построение В-дерева: 6 11 3 12 14 2 10 5 4 7 8 13 1 9
Описание слайда:
Построение В-дерева: 6 11 3 12 14 2 10 5 4 7 8 13 1 9

Слайд 10


Построение В-дерева: 6 11 3 12 14 2 10 5 4 7 8 13 1 9
Описание слайда:
Построение В-дерева: 6 11 3 12 14 2 10 5 4 7 8 13 1 9

Слайд 11


Построение В-дерева: 6 11 3 12 14 2 10 5 4 7 8 13 1 9
Описание слайда:
Построение В-дерева: 6 11 3 12 14 2 10 5 4 7 8 13 1 9

Слайд 12


Построение В-дерева: 6 11 3 12 14 2 10 5 4 7 8 13 1 9
Описание слайда:
Построение В-дерева: 6 11 3 12 14 2 10 5 4 7 8 13 1 9

Слайд 13


Построение В-дерева: 6 11 3 12 14 2 10 5 4 7 8 13 1 9
Описание слайда:
Построение В-дерева: 6 11 3 12 14 2 10 5 4 7 8 13 1 9

Слайд 14


Построение В-дерева: 6 11 3 12 14 2 10 5 4 7 8 13 1 9
Описание слайда:
Построение В-дерева: 6 11 3 12 14 2 10 5 4 7 8 13 1 9

Слайд 15


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

Слайд 16


Запись В-дерева на диск Общее предназначение В-дерева состоит в сохранении данных на диске В-дерево должно сохранить на диске страницы, индексы и данные
Описание слайда:
Запись В-дерева на диск Общее предназначение В-дерева состоит в сохранении данных на диске В-дерево должно сохранить на диске страницы, индексы и данные

Слайд 17


Размер страниц Цель: быстрое считывание с диска Большинство ПК работает быстрее, если считываются блоки размером кратным 2 Идеальный размер определяется размером сектора жесткого диска
Описание слайда:
Размер страниц Цель: быстрое считывание с диска Большинство ПК работает быстрее, если считываются блоки размером кратным 2 Идеальный размер определяется размером сектора жесткого диска

Слайд 18


Размер страниц Будем рассматривать размер – 512 Каждая запись индекса должна быть делителем порядка, чтобы на каждой странице помещалось четное число Длина индекса будет составлять 16 байтов: 4 байта на указатель (теперь смещение) и 11 байтов на данные, с завершающим строку байтом NULL.
Описание слайда:
Размер страниц Будем рассматривать размер – 512 Каждая запись индекса должна быть делителем порядка, чтобы на каждой странице помещалось четное число Длина индекса будет составлять 16 байтов: 4 байта на указатель (теперь смещение) и 11 байтов на данные, с завершающим строку байтом NULL.

Слайд 19


Размер страниц На странице размером 512 байтов существует 32 набора по 16 байтов (т.е.32 объекта индекса). Порядок В-дерева составляет 32. 32-порядковое дерево может содержать 1024 слова в двух уровнях, 32768 слов в трех уровнях и 33554432 слов в пяти уровнях. В большинстве случаев поиск может завершиться за несколько обращений к жесткому диску, что идеально..
Описание слайда:
Размер страниц На странице размером 512 байтов существует 32 набора по 16 байтов (т.е.32 объекта индекса). Порядок В-дерева составляет 32. 32-порядковое дерево может содержать 1024 слова в двух уровнях, 32768 слов в трех уровнях и 33554432 слов в пяти уровнях. В большинстве случаев поиск может завершиться за несколько обращений к жесткому диску, что идеально..

Слайд 20


Количество страниц, которые одновременно могут находиться в памяти для определения числа страниц, которые одновременно могут находиться в памяти необходимо сделать обход начинающаяся с верхнего узла и прокладывающая себе путь вниз по дереву. Поскольку каждая страница может содержать 32 индекса, то в любое время половина из них будет задействована: 16 индексов на страницу. 10 уровней страниц с 16 индексами на страницу предоставляют триллион ключей.
Описание слайда:
Количество страниц, которые одновременно могут находиться в памяти для определения числа страниц, которые одновременно могут находиться в памяти необходимо сделать обход начинающаяся с верхнего узла и прокладывающая себе путь вниз по дереву. Поскольку каждая страница может содержать 32 индекса, то в любое время половина из них будет задействована: 16 индексов на страницу. 10 уровней страниц с 16 индексами на страницу предоставляют триллион ключей.

Слайд 21


Количество страниц, которые одновременно могут находиться в памяти 10 страниц, впрочем, занимают всего лишь 2 Кб памяти. (16 байтов на индекс умножить на 16 байтов на страницу и умножить на 10 страниц, равно 2560 байтов, или 2 Кб.) Вот и мощь В-деревьев: постоянно занимая в памяти всего 2 Кб, они обеспечивают доступ к триллиону ключей!
Описание слайда:
Количество страниц, которые одновременно могут находиться в памяти 10 страниц, впрочем, занимают всего лишь 2 Кб памяти. (16 байтов на индекс умножить на 16 байтов на страницу и умножить на 10 страниц, равно 2560 байтов, или 2 Кб.) Вот и мощь В-деревьев: постоянно занимая в памяти всего 2 Кб, они обеспечивают доступ к триллиону ключей!

Скачать

Теги B-деревья
Похожие презентации
Mypresentation.ru
Загрузить презентацию