B-деревья. Алгоритмы и структуры данных

1.

B-деревья
Если дерево поиска хранится на диске, то задача ускорения поиска включает в себя
задачу минимизации числа обращений к диску. Это означает, что данные надо
хранить в блоках некоторого стандартного размера, кратного физическому размеру
блока на магнитном носителе.
Двоичное дерево не позволяет разумно организовать группировку данных так, чтобы
при поиске сравнения группировались вокруг данных одного блока.
15
7
23
4
1
10
5
8
20
13
17
Кубенский А.А. Алгоритмы и структуры данных.
Глава 4. Иерархические структуры данных.
29
22
27
31
1

2.

Обобщение 2-3-дерева – В-дерево k-го порядка
Пример структуры при k = 3
Структура В-дерева:
Корневой узел содержит от 1 до 2*k ключей
Прочие узлы содержат от k до 2*k ключей
Ключи упорядочены (возможен быстрый поиск)
Промежуточные узлы имеют все ссылки
(корень – от 2, остальные – от (k+1) до (2*k+1) ссылки)
Все терминальные узлы (листья) находятся на одном уровне
Кубенский А.А. Алгоритмы и структуры данных.
Глава 4. Иерархические структуры данных.
2

3.

Вставка нового ключа в В-дерево.
1. Если блок ключей неполон, то возможно добавление нового ключа в неполный блок.
n < 2k ключей
2. Если блок ключей полон, но есть соседний неполный блок, то возможно
«переливание» одного ключа в соседний блок.
Кубенский А.А. Алгоритмы и структуры данных.
Глава 4. Иерархические структуры данных.
3

4.

Вставка нового ключа в В-дерево расщеплением узла.
3. Если блок ключей полон, и соседние с ним блоки тоже полны, то необходимо
делать расщепление блока.
k кл.
(2 * k +11) ключ
k кл.
При вставке ключа в терминальный узел образовалось переполнение узла
Делим узел на 3 узла: k, 1 и k ключей
Перемещаем средний ключ на предыдущий уровень
При расщеплении терминального узла, возможно, придется добавлять
в нетерминальные узлы ключи вместе с поддеревьями. При этом опять возможно
сделать это путем пополнения блока, переливания и расщепления (см. след. слайд).
Кубенский А.А. Алгоритмы и структуры данных.
Глава 4. Иерархические структуры данных.
4

5.

Вставка ключа в нетерминальный узел.
1. Пополнение блока.
n < 2k ключей
2. Переливание.
Кубенский А.А. Алгоритмы и структуры данных.
Глава 4. Иерархические структуры данных.
5

6.

Расщепление нетерминального узла.
k
1
k
Кубенский А.А. Алгоритмы и структуры данных.
Глава 4. Иерархические структуры данных.
6

7.

Удаление ключа из B-дерева.
1. Замена удаляемого ключа на ключ, лежащий в терминальном узле.
Кубенский А.А. Алгоритмы и структуры данных.
Глава 4. Иерархические структуры данных.
7

8.

Удаление ключа из B-дерева.
2. Удаление ключа из терминального узла путем уменьшения размера узла, «займа»
с переливанием или слияния узлов.
а) уменьшение размера узла:
k
1kузлов
узл ов
б) переливание с займом из
соседнего узла:
k узл ов
k узл ов
k узл ов
б) слияние узлов:
Слияние узлов может
привести к удалению
ключей в промежуточных
узлах, вплоть до корневого.
Кубенский А.А. Алгоритмы и структуры данных.
Глава 4. Иерархические структуры данных.
k узл
2 kовузл ов
k узл ов
8

9.

Структура блока.
Промежуточный
узел
Ключ
Ссылка на
левое поддерево
Ссылка на данные
Ссылка на следующее
поддерево
Лист
Ключ
Ссылка на данные
Кубенский А.А. Алгоритмы и структуры данных.
Глава 4. Иерархические структуры данных.
9

10.

В+ дерево: структура блока.
Копия
ключа
Ссылка на
левое поддерево
Промежуточный
узел
Ссылка на правое
поддерево
Лист
Ключ
Ссылка на данные
Кубенский А.А. Алгоритмы и структуры данных.
Глава 4. Иерархические структуры данных.
Ссылка на
следующий
лист
10

11.

Общая структура B+ дерева
21 37
7 12
1 3 4 6
7 10
21 26
12 14
15 17 19
Кубенский А.А. Алгоритмы и структуры данных.
Глава 4. Иерархические структуры данных.
21 24
37 43
26 29
32 35
37 40 42
43 46
11

12.

Выполнение операций в B+ дереве
Изменения в выполнении вставки и удаления узлов.
1. Переливание
Добавление узла
Перемещение
Копирование
12
15
12
2. Расщепление
Разделение узла на два
Копирование ключа
Сдвиг копии и образование
новых ссылок
k кл.
(2 * k +11) ключ
k+1 кл.
На промежуточных узлах все операции происходят как и раньше.
Кубенский А.А. Алгоритмы и структуры данных.
Глава 4. Иерархические структуры данных.
12

13.

Особенности B+ дерева
При удалении ключей могут оставаться копии удаленных ключей. Это никак не
влияет на алгоритм и результат поиска.
Преимущества структуры В+ дерева перед В деревом:
1. Унификация структуры узлов;
2. Наличие сквозного списка ключей позволяет легко находить отрезки данных.
Некоторое усложнение работы операций по вставке и удалению ключей влияет
на общую скорость работы незначительно, поскольку не связано с дополнительными
операциями чтения/записи данных.
Кубенский А.А. Алгоритмы и структуры данных.
Глава 4. Иерархические структуры данных.
13