B-деревья

Сентябрь 7, 2022

Содержание

2. Определение В-дерево изобретено в 1972г. Р.Байером и Е. Маккрайтом Предназначено для создания мелких деревьев для быстрого
3. Определение В-дерево состоит из страниц. Каждая страница имеет набор индексов. Каждый индекс содержит значение ключа и
4. Определение Страница называется узловой, если индекс страницы указывает на другую страницу Страница называется листовой если индекс
5. Определение Каждая страница максимально может иметь количество дочерних страниц, равное ее порядку. Для В-деревьев существует правило:
6. Определение Новые индексы всегда добавляются в листовые страницы. Вы никогда не добавляете индекс к узловой странице.
7. Построение В-дерева: 1. 6 11 3 12 14 2 10 5 4 7 8 13 1
8. Построение В-дерева: 2-3. 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
11. Построение В-дерева: 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
13. Построение В-дерева: 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
15. Алгоритм добавления новой страницы Разбить страницу пополам. Добавить новый ключ в подходящую позицию Установить соответственно указатель.
16. Запись В-дерева на диск Общее предназначение В-дерева состоит в сохранении данных на диске В-дерево должно сохранить
17. Размер страниц Цель: быстрое считывание с диска Большинство ПК работает быстрее, если считываются блоки размером кратным
18. Размер страниц Будем рассматривать размер – 512 Каждая запись индекса должна быть делителем порядка, чтобы на
19. Размер страниц На странице размером 512 байтов существует 32 набора по 16 байтов (т.е.32 объекта индекса).
20. Количество страниц, которые одновременно могут находиться в памяти для определения числа страниц, которые одновременно могут находиться
22. Скачать презентацию

Слайд 2

Определение
В-дерево изобретено в 1972г. Р.Байером и Е. Маккрайтом
Предназначено для создания мелких

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

Слайд 3

Определение
В-дерево состоит из страниц.
Каждая страница имеет набор индексов.
Каждый индекс

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

Слайд 4

Определение
Страница называется узловой, если индекс страницы указывает на другую страницу
Страница

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

Слайд 5

Определение
Каждая страница максимально может иметь количество дочерних страниц, равное ее порядку.
Для

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

Слайд 6

Определение
Новые индексы всегда добавляются в листовые страницы.
Вы никогда не добавляете

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

Слайд 7

Построение В-дерева: 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

Корень

Заполненная листовая страница

Разбиваем страницу на две

Слайд 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

Корень

Разбиваем страницу

Слайд 11

Построение В-дерева:
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

Корень

Добавляем новые элементы

Разбиваем заполненные страницы и добавляем указатель к верхней

Слайд 13

Построение В-дерева:
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

Корень

Разбиваем верхнюю страницу

Слайд 15

Алгоритм добавления новой страницы
Разбить страницу пополам.
Добавить новый ключ в подходящую позицию

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

Слайд 16

Запись В-дерева на диск
Общее предназначение В-дерева состоит в сохранении данных на

диске
В-дерево должно сохранить на диске страницы, индексы и данные

Слайд 17

Размер страниц
Цель: быстрое считывание с диска
Большинство ПК работает быстрее, если

считываются блоки размером кратным 2
Идеальный размер определяется размером сектора жесткого диска

Слайд 18

Размер страниц
Будем рассматривать размер – 512
Каждая запись индекса должна быть

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

Слайд 19

Размер страниц
На странице размером 512 байтов существует 32 набора по

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

Слайд 20

Количество страниц, которые одновременно могут находиться в памяти
для определения числа страниц,

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

B-деревья

Содержание

ОпределениеВ-дерево изобретено в 1972г. Р.Байером и Е. МаккрайтомПредназначено для создания мелких

ОпределениеВ-дерево состоит из страниц. Каждая страница имеет набор индексов. Каждый индекс

ОпределениеСтраница называется узловой, если индекс страницы указывает на другую страницу Страница

ОпределениеКаждая страница максимально может иметь количество дочерних страниц, равное ее порядку.Для

ОпределениеНовые индексы всегда добавляются в листовые страницы. Вы никогда не добавляете

Построение В-дерева: 1.6 11 3 12 14 2 10 5 4 7

Построение В-дерева: 2-3.6 11 3 12 14 2 10 5 4 7

Построение В-дерева: 6 11 3 12 14 2 10 5 4 7

Построение В-дерева: 6 11 3 12 14 2 10 5 4 7

Построение В-дерева: 6 11 3 12 14 2 10 5 4 7

Построение В-дерева: 6 11 3 12 14 2 10 5 4 7

Построение В-дерева: 6 11 3 12 14 2 10 5 4 7

Построение В-дерева: 6 11 3 12 14 2 10 5 4 7

Алгоритм добавления новой страницыРазбить страницу пополам.Добавить новый ключ в подходящую позицию

Запись В-дерева на дискОбщее предназначение В-дерева состоит в сохранении данных на

Размер страниц Цель: быстрое считывание с дискаБольшинство ПК работает быстрее, если

Размер страниц Будем рассматривать размер – 512Каждая запись индекса должна быть

Размер страниц На странице размером 512 байтов существует 32 набора по

Количество страниц, которые одновременно могут находиться в памятидля определения числа страниц,

Похожие презентации

Определение
В-дерево изобретено в 1972г. Р.Байером и Е. Маккрайтом
Предназначено для создания мелких

Определение
В-дерево состоит из страниц.
Каждая страница имеет набор индексов.
Каждый индекс

Определение
Страница называется узловой, если индекс страницы указывает на другую страницу
Страница

Определение
Каждая страница максимально может иметь количество дочерних страниц, равное ее порядку.
Для

Определение
Новые индексы всегда добавляются в листовые страницы.
Вы никогда не добавляете

Построение В-дерева: 1.
6 11 3 12 14 2 10 5 4 7

Построение В-дерева: 2-3.
6 11 3 12 14 2 10 5 4 7

Построение В-дерева:
6 11 3 12 14 2 10 5 4 7

Построение В-дерева:
6 11 3 12 14 2 10 5 4 7

Построение В-дерева:
6 11 3 12 14 2 10 5 4 7

Построение В-дерева:
6 11 3 12 14 2 10 5 4 7

Построение В-дерева:
6 11 3 12 14 2 10 5 4 7

Построение В-дерева:
6 11 3 12 14 2 10 5 4 7

Алгоритм добавления новой страницы
Разбить страницу пополам.
Добавить новый ключ в подходящую позицию

Запись В-дерева на диск
Общее предназначение В-дерева состоит в сохранении данных на

Размер страниц
Цель: быстрое считывание с диска
Большинство ПК работает быстрее, если

Размер страниц
Будем рассматривать размер – 512
Каждая запись индекса должна быть

Размер страниц
На странице размером 512 байтов существует 32 набора по

Количество страниц, которые одновременно могут находиться в памяти
для определения числа страниц,