Рис. 19.4 Б-дерево высоты 3 содержит минимально возможное число ключей. Внутри каждой вершины х записано число п[х] ключей в ней.

19.1-3 Найти все Б-деревья минимальной степени 2, представляющие множество {1, 2, 3,4, 5}

19.1-4 Найти точную верхнюю оценку для числа ключей, хранящихся в Б-дереве высоты h и минимальной степени t.

19.1-5 Описать структуру данных, которая получится, если в красно-чёрном дереве каждую чёрную вершину соединить с ее красными детьми, а их детей сделать детьми этой чёрной вершины.

19.2. Основные операции с Б-деревьями

В этом разделе мы подробно рассмотрим операции B-Tree-Search (поиск), B-Tree-Create (создание Б-дерева) и B-Tree-Insert (добавление элемента). Мы считаем, что:

•Корень Б-дерева всегда находится в оперативной памяти, т.е. операция Disk-Read для корня никогда не требуется; однако всякий раз, когда мы изменяем корень, мы должны его сохранять на диске.

•Все вершины, передаваемые как параметры, уже считаны с диска.

Наши процедуры обрабатывают дерево за один проход от корня к листьям.

Поиск в Б-дереве

Поиск в Б-дереве похож на поиск в двоичном дереве. Разница в том, что в каждой вершине х мы выбираем один вариант из

(га[ж] + 1), а не из двух.

Как и процедура Tree-Search (для двоичных деревьев), рекурсивной процедура B-Tree-Search получает на вход указатель х на корень поддерева и ключ к, который мы ищем в этом поддереве. Для поиска ключа к в Б-дереве Г следует скомандовать B-Tree-Search(гоо£(Т), к), где root(T) указывает на корень. Если процедура обнаруживает ключ к в дереве, она возвращает пару (у, г), где у - вершина, г - порядковый номер указателя, для которого keyi[y] = к. В противном случае процедура возвращает константу nil.

B-Tree-Search, к) 1

2while г п[х] and к > keyi[x]

3do г <- г + 1

4if г п[х] and к = keyi[x]

5then return (ж,г)

6if leaj[x]

7then return nil

8else DlSK-READ(c;[a:])

9return B-Tree-Search(c8], k)

В строках 1-3 ищется наименьшее г, для которого к keyi[x]; если такого нет, то в г помещается п[х] +1 (линейный поиск). Если нужный ключ найден, работа прекращается (строки 4-5). Затем (строки 6-7) программа либо останавливается, если поиск завершился безрезультатно (ж - лист), либо рекурсивно вызывает себя, предварительно считав с диска корень нужного поддерева (строки 8-9).

На рис. 19.1 показана работа этой программы. Светлые вершины просмотрены при поиске буквы R.

Как и процедура Tree-Search, наша программа просматривает вершины дерева от корня к листу. Поэтому число обращений к диску есть в(h) = 0(logf га), где h - высота дерева, а га - количество ключей. Так как га[ж] 2t, то цикл while в строках 2-3 повторяется O(t) раз, и время вычислений равно O(th) = 0(t\ogt га).

Создание пустого Б-дерева

При работе с Б-деревом Г, мы сначала создаем с помощью процедуры B-Tree-Create пустое дерево, а затем записываем в него данные с помощью процедуры B-Tree-Insert. Обе эти процедуры используют подпрограмму Allocate-Node, которая находит место на диске для новой вершины. Мы считаем, что подпрограмма Allocate-Node требует времени 0(1) и не использует операцию Disk-Read.

Рис. 19.5 Разбиение вершины дерева минимальной степени t = 4. Делим вершину у на две: у и г. Ключ-медиана S вершины у переходит к ее родителю х.

B-Tree-Create(T)

1ж <- Allocate-Node()

2leaj[x] <- true

3п[х] <- О

4Disk-Write)

5root[T] <- ж

Процедура B-Tree-Create требует одного обращения к диску, время работы - 0(1).

Разбиение вершины Б-дерева на две

Добавление элемента в Б-дерево - значительно более сложная операция, чем добавление элемента в двоичное дерево поиска. Ключевым местом является разбиение (splitting) полной (с 2t - 1 ключами) вершины у на две вершины, имеющие по t - 1 элементов в каждой. При этом ключ-медиана (median key) keyt[y] отправляется к родителю ж вершины у и становится разделителем двух полученных вершин. Это возможно, если вершина ж неполна. Если у - корень, процедура работает аналогично. В этом случае высота дерева увеличивается на единицу. Таков механизм роста Б-дерева.

Процедура B-Tree-Split-Child делит вершину у на две и меняет соответствующим образом её родителя ж. На рис. 19.5 показано, как это происходит. Ключ-медиана S вершины у переходит к её родителю ж, а большие S элементы переписываются в нового ребенка z вершины ж. Входными данными процедуры являются неполная внутренняя вершина ж, число г и полная вершину у, для которых у = сг[ж]. Мы считаем, что вершины хну уже находятся в оперативной памяти.