Рис. 19.3 Б-дерево высоты 2 содержит более миллиарда ключей. Каждая вершина содержит 1000 ключей. Всего имеется 1001 вершина на глубине 1 и более миллиона листьев на глубине 2. В каждой вершине х записано число п[х] ключей в ней.

памяти лишь небольшую часть всей информации (фиксированное число секторов), и поэтому её размер не ограничивается размером доступной памяти.

Мы рассматриваем диск как большой участок памяти, работа с которым происходит следующим образом: перед тем как работать с объектом ж, мы должны выполнить специальную операцию Disk-Read (ж) (чтение с диска). После внесения изменений в наш объект ж, мы выполняем операцию Disk-Write) (запись на диск):

1...

2ж <- указатель на какой-то объект

3Disk-Read)

4операции, которые используют и/или изменяют

поля объекта, на который указывает ж.

5Disk-Write) > Не нужно, если

> поля объекта не изменились.

6операции, которые пользуются полями указателя ж,

но не меняют их.

7...

Время работы программы в основном определяется количеством операций Disk-Read и Disk-Write, так что имееет смысл читать/записывать возможно больше информации за раз и сделать так, чтобы вершина Б-дерева заполняла полностью один сектор диска. Таким образом, степень ветвления (число детей вершины) определяется размером сектора.

Типичная степень ветвления Б-деревьев находится между 50 и 2000 (в зависимости от размера элемента). Увеличение степени ветвления резко сокращает высоту дерева, и тем самым число обращений к диску, при поиске. На рис. 19.3 показано Б-дерево степени 1001 и высоты 2, хранящее более миллиарда ключей. Учитывая, что корень можно постоянно хранить в оперативной памяти, достаточно двух обращений к диску, при поиске нужного ключа!

19.1. Определение Б-дерева

Как и раньше, для простоты мы считаем, что дополнительная информация, связанная с ключом, хранится в той же вершине де-

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

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

Итак, Б-деревом (B-tree) назовём корневое дерево, устроенное следующим образом:

1.Каждая вершина х содержит поля, в которых хранятся:

а), количество п[х] ключей, хранящихся в ней;

б), сами ключи keyi[x] кеу2[х] ... кеуп[х] (в неубывающем порядке)

в), булевское значение leaj[x], истинное, когда вершина х является листом.

2.Если х - внутренняя вершина, то она также содержит п[х] + 1 указатель с\[х], с2[х],..., сга[г,] 1[ж] на её детей. У листьев детей нет, и эти поля для них не определены.

3.Ключи keyi[x] служат границами, разделяющими значения ключей в поддеревьях:

ki кеух[х] к2 кеу2[х] • • • кеуп[х][х\ кп[х]+1,

где к{ - любой из ключей, хранящихся в поддереве с корнем сг[х].

4.Все листья находятся на одной и той же глубине (равной высоте h дерева).

5.Число ключей, хранящихся в одной вершине, ограничено сверху и снизу; границы задаются единым для всего дерева числом t 2, которое называется минимальной степенью (minimum degree) Б-дерева. Именно:

а). Каждая вершина, кроме корня, содержит по меньшей мере t-1 ключ. Таким образом, внутренние вершины (кроме корня) имеют не менее t детей. Если дерево непусто, то в корне должен храниться хотя бы один ключ.

всегда удобно, и в реальном алгоритме

б). В вершине хранится не более 2t - 1 ключей. Следовательно, внутренняя вершина имеет не более 2t детей. Вершину, хранящую ровно 2t - 1 ключей, назовем полной (full).

В простейшем случае t = 2, тогда у каждой внутренней вершины 2, 3 или 4 ребенка, и мы получаем так называемое 2-3-4 дерево (2-34 tree). (Как мы уже говорили, для эффективной работы с диском на практике t надо брать гораздо большим.)

Высота Б-дерева

Число обращений к диску для большинства операций пропорционально высоте Б-дерева. Оценим сверху эту высоту.

Теорема 19.1. Для всякого Б-дерева Т высоты h и минимальной степени t 2, хранящего га 1 ключей, выполнено неравенство

h s 1 11 + 1 h l°gf --.

Доказательство. Пусть высота Б-дерева равна заданному числу h. Наименьшее число вершин в дереве будет, если степень каждой вершины минимальна, то есть у корня 2 ребёнка, а у внутренних вершин по t детей. В этом случае на глубине 1 мы имеем 2 вершины, на глубине 2 имеем 2t вершин, на глубине 3 имеем 2t2 вершин, ... , на глубине h имеем 2th~1 вершин. При этом в корне хранится один ключ, а во всех остальных вершинах по t - 1 ключей. (На рис. 19.4 показано такое дерево при h чаем неравенство:

h

га 1 + (t - 1) Y 2~1 = 1 + 2(* -

8 = 1

откуда следует утверждение теоремы.

Как и для красно-чёрных деревьев, высота Б-дерева с га вершинами есть О (log га), но основание логарифма для Б-деревьев гораздо больше, что примерно в lg 4 раз сокращает количество обращений к диску.

Упражнения

19.1-1 Почему в определении Б-дерева требование t 2 существенно?

19.1-2 При каких t дерево на рис. 19.1 можно рассматривать как Б-дерево минимальной степени tl

3.) Таким образом, полу-

th - 1

□