Слайд 2Б-деревья
Б-деревья – сбалансированные деревья, обеспечивающие
эффективное хранение информации на дисках и
других
устройствах с прямым доступом.
Каждая вершина x в Б-дереве хранит
n(x)- элементов (ключей)
и имеет n(x)+1 детей.
Ключи служат границами, разделяющими всех ее потомков на
n(x)+1 групп.
При поиске в Б-дереве мы сравниваем искомый ключ с
n(x)- ключами из x и по результатам сравнения выбираем один из
n(x)+1-путей.
Слайд 3M
D H
Q T X
B C
F G
N P
J K L
R S
V
W
Y Z
t = 2
Полные вершины
Пример Б-дерева
Слайд 4Определение Б-дерева
Для простоты будем считать, что вся дополнительная информация, связанная
с ключами храниться в той же вершине дерева (на практике
это не всегда так).
Б-дерево – корневое дерево, устроенное следующим образом:
Каждая вершина x содержит поля, в которых хранятся:
а) n - количество ключей, хранящихся в данной вершине;
б) сами ключи k0 ≤ k1 ≤ … ≤ kn-1 в неубывающем порядке;
в) булевское значегие leaf[x], истинное, если вершина x - лист;
2. Если x – внутренняя вершина, то она также содержит n(x)+1-указателей: C0, C1,…, Cn(x) на ее детей;
Слайд 5Определение Б-дерева(продолжение)
3. Ключи keyi[x] служат границами, разделяющими значения ключей в
поддеревьях:
k0 ≤ key0[x] ≤ k1 ≤ key2[x] ≤...
≤ keyn[x]-1[x] ≤ Kn[x], где ki - множество ключей, хранящихся в поддереве с корнем Ci[x];
4. Все листья находятся на одной и той же глубине, равной высоте дерева;
5. Число ключей, хранящихся в одной вершине, ограничено сверху и снизу единым для Б-дерева числом t ≥ 2, которое называется - минимальной степенью Б-дерева. А именно:
Слайд 6Определение Б-дерева (продолжение)
а) каждая вершина, кроме корня содержит по меньшей
мере t-1
ключей. Т.о. внутренняя вершина(кроме корня) имеет t-детей.
Если дерево
не пусто, то в корне должен храниться хотя бы один
ключ.
б) В каждой вершине хранится не более 2t-1 ключей, внутренняя
вершина имеет не более 2t-детей . Вершину, хранящую 2t-1
ключей, называют полной.
Например, t = 2, то у каждой вершины 2, 3 или 4 ребенка.
Такое дерево называется 2-3-4 деревом.
Для эффективной работы t надо брать гораздо большим.
Слайд 71000
1000
1000
1000
1000
1000
1000
….
1001
….
1001
…..
1001
….
1001
………
………
1 вершина – 1000 ключей
1001 вершина – 1001000 ключей
1 002
001 вершина -1 002 001 000 ключей
Б-дерево высоты 2 –
содержит более миллиарда ключей.
Каждая вершина содержит 1000 ключей.
Более миллиона листьев на глубине 2.
Слайд 8У таких деревьев, как правило, только корень
находиться в ОП, остальное
дерево – на диске.
Диск разбит на сектора (дорожки на сектора).
Обычно записывают или считывают сектор целиком.
Время доступа, чтобы подвести головку к нужному месту на
диске, может быть достаточно большим (до 20 миллисекунд).
Как только головка диска установлена, запись или чтение
происходит довольно быстро.
Часто получатся, что обработка прочитанного занимает меньше
времени, чем поиск нужного сектора.
Важно количество обращений к диску!
Слайд 9Реализация в ОП
typedef struct tree{
int n; //количество ключей
int *key; //key[0]
…
детей: Ci(x).
Слайд 10Создание корня дерева
B_tree *B;
B=(B_tree*) malloc (sizeof(B_tree));
B->key=(int*) malloc (sizeof(int));
B->n=1;
(B->key)[0]=‘M’;
B->child=NULL;
M
Слайд 11Создание дерева
B->child = (B_tree**)malloc(sizeof(B_tree*)*2);
B->child)[0]=(B_tree*)malloc(sizeof(B_tree));
B->child)[1]=(B_tree*)malloc(sizeof(B_tree));
x=(B->child)[0];
x->n=2;
(x->key)=(int*)malloc(2*sizeof(int));
(x->key)[0]=‘D’;
(x->key)[1]=‘H’;
X->child=NULL;
Аналогичные действия для вершины:
QTX
Слайд 12 Можно выполнить реализацию с использованием файлов, где каждый ребенок есть
отдельный файл.
В общем случае можно считать, что:
имеется операция Disk_READ(x)
– чтение с диска;
Diks_Write(x) – запись на диск.
Учитываем только количество обращений к диску!
Слайд 13Теорема. Для любого Б-дерева высоты h и минимальной степени t
≥ 2, хранящего n ≥ 1 ключей, выполнено неравенство:
Высота Б-дерева
с n-вершинами есть O(log n),
но основание логарифма для Б-дерева гораздо больше,
что примерно в log t раз сокращает количество обращений
к диску.
Глубина вершины - путь из корня в вершину.
Высота (уровень) – max путь из вершины в лист.
Слайд 14Алгоритм поиска
Поиск в Б-дереве похож на поиск в двоичном дереве.
Разница в том, что в вершине x мы выбираем один
вариант
из (n(x)+1), а не из двух.
Процедура поиска получает на вход указатель х на
корень поддерева и ключ k, который мы ищем в этом
поддереве.
Если процедура обнаруживает в дереве ключ k, то она
возвращает пару (y, i), где у - вершина, i - порядковый номер
указателя, для которого keyi(y) = k.
Иначе операция возвращает NULL.
Слайд 15Реализация поиска
B_tree_search(x,k){
int i = 0;
while ((i < n(x)) && (k > keyi(x)))
i++;
if
((i
Слайд 16Разбиение вершины Б-дерева
Добавление эелемента в Б-дерево – более сложная
операция
по сравнению с бинарными деревьями.
Ключевым местом является разбиение полной (с
2t-1
ключами ) вершины на две вершины, имеющие по t-1
ключей в каждой.
При этом ключ-медиана keyt1(y) отправляется к родителю x
вершины y и становится разделителем двух полученных
вершин. Это возможно, если вершина х неполна.
Если y – корень, то высота дерева увеличивается на 1.
Слайд 17Пример
…N W…
P Q R S T U V
… N
S W …
P Q R
T U V
x
y= Ci(x)
y= Ci(x)
z=
Ci+1(x)
Keyi-1(x)
Keyi(x)
Keyi-1(x)
Keyi(x)
Keyi+1(x)
Ci(x)- укакзатель на i –го ребенка в x
Минимальная степень t=4.
Делим вершину y на две: y и z. Ключ
медиана S вершины y переходит к ее
родителю x . Ключи, больше S,
переписываются в нового ребенка z
вершины x.
Слайд 18
Входные данные: неполная внутренняя вершина х, число i
и
полная вершина y: y = Сi(x) (cчитаем, что x и
y уже в ОП).
B_tree_SPLIT_Child (x, i, y)
{
z – создать узел;(файл,отвести место).
leaf(z)=leaf(y);
n(z)=t-1;
for(j=0;j keyj(z)=keyj+t(y);
if (!leaf(y))
for(j=0;j Cj(z)= Cj+t(y);
n(y)=t-1;
Слайд 19 for(j=n(x)+1; j ≤ i; j--)
Cj+1(x)= Cj(x);
Ci+1[x]=z;
for(j=n(x);
j ≤ i; j--)
keyj+1(x)=keyj(x);
keyi(x)=keyj(y);
n(x)=n(x)+1;
Переписать вершины: y, z,
x. (Disk_Write [x])
}
Вершина y-имела 2t-детей, после разбиения в ней осталось t- детей. Остальные t-детей стали детьми новой вершины z.
Слайд 20Добавление элемента в Б-дерево
Процедура B_tree_insert (T, k) – добавляет элемент
k в
Б-дерево T, пройдя один раз от корня к
листу.
На это требуется время 0(t logtn) и 0(h)-обращений к диску,
если высота дерева равна h.
По ходу дела с помощью процедуры B_tree_Split_child
разделяются вершины, которые являются полными и которые
имеют неполного родителя.
В результате, доходим до неполного листа, куда и добавляем
новый элемент.
Слайд 21B_tree_insert (T, k) {
// добавление в дерево с полным
корнем
r = root(T);
if (n(r)== 2t-1){
s= выделяем память/файл для нового
узла;
root(T)= s; //он становится корнем leaf(s)= 0;
n(s)= 0;
C1(s)= r;
B_tree_split_child (S, 1, r);
B_tree_insert_nonfull (s, k);//добавляет
} // элемент в k в поддерево с корнем в неполной
else //вершине
B_tree_insert_nonfull (r, k);
}
Слайд 22Добавление элемента в неполную вершину
B_tree_insert_nonfull (r, k)-
рекурсивно вызывает себя, при
необходимости, выполнив
разделение.
Если вершина x – лист, то ключ k
в него добавляется.
Иначе k добавляется к поддереву, корень которого является
ребенком x. Для этого определяется нужный ребенок вершины x.
Если ребенок – полная вершина, то он разделяется.
Слайд 23B_tree_insert_nonfull(x, k){
i = n(x);
if leaf(x){ // ключ вставляется в лист
while((i≥0)&&(k
= n(x)+1;
Disk_WRITE (x);
}
else {while((i ≥ 0) &&(k < keyi(x)))
i--; // поиск нужного ребенка
Слайд 24 i= i+1;
Disk_READ(Ci(x));
if (n(Ci(x))== 2t-1)
//если ребенок–полная
вершина
B_tree_split_child (x, i, Ci(x));
// разделение
if (k > keyi(x)) i=i+1;
B_tree_ insert_nonfull (Ci(x),
k);
}
Слайд 26(в) удалена M из внутренней
вершины, ребенок которой имеет
не менее
t элементов
Если ребенок, следующий за удаляемым ключом, имеет не менее
t элементов,
Поступаем аналогично (в)
B
N O
Q R S
Y Z
U V
(д) удалена D, в вершине
х нет
ключа D и t = 2
![Определение Б-дерева(продолжение)3. Ключи keyi[x] служат границами, разделяющими значения ключей в поддеревьях: k0 ≤ key0[x] ≤ k1](/img/thumbs/72b2e097a19e57548f5ad819a4f40883-800x.jpg "Б-деревья Определение Б-дерева(продолжение)3. Ключи keyi[x] служат границами, разделяющими значения ключей в поддеревьях:")
![Реализация в ОПtypedef struct tree{ int n; //количество ключей int *key; //key[0]](/img/tmb/3/238312/1d381c9c210d933dd84383beac0e8f0e-800x.jpg "Б-деревья Реализация в ОПtypedef struct tree{ int n; //количество ключей int *key; //key[0]")
![Создание корня дерева B_tree *B;B=(B_tree*) malloc (sizeof(B_tree));B->key=(int*) malloc (sizeof(int));B->n=1;(B->key)[0]=‘M’;B->child=NULL; M](/img/thumbs/12ea7444523ed1d050842a78f6845eeb-800x.jpg "Б-деревья Создание корня дерева B_tree *B;B=(B_tree*) malloc (sizeof(B_tree));B->key=(int*) malloc (sizeof(int));B->n=1;(B->key)[0]=‘M’;B->child=NULL; M")
![Создание дереваB->child = (B_tree**)malloc(sizeof(B_tree*)*2);B->child)[0]=(B_tree*)malloc(sizeof(B_tree));B->child)[1]=(B_tree*)malloc(sizeof(B_tree));x=(B->child)[0];x->n=2;(x->key)=(int*)malloc(2*sizeof(int));(x->key)[0]=‘D’;(x->key)[1]=‘H’;X->child=NULL;Аналогичные действия для вершины: QTX](/img/thumbs/1afdb8712c39e4d41bbe196f77013d55-800x.jpg "Б-деревья Создание дереваB->child = (B_tree**)malloc(sizeof(B_tree*)*2);B->child)[0]=(B_tree*)malloc(sizeof(B_tree));B->child)[1]=(B_tree*)malloc(sizeof(B_tree));x=(B->child)[0];x->n=2;(x->key)=(int*)malloc(2*sizeof(int));(x->key)[0]=‘D’;(x->key)[1]=‘H’;X->child=NULL;Аналогичные действия для вершины: QTX")
![for(j=n(x)+1; j ≤ i; j--) Cj+1(x)= Cj(x); Ci+1[x]=z; for(j=n(x); j ≤ i; j--) keyj+1(x)=keyj(x); keyi(x)=keyj(y); n(x)=n(x)+1;](/img/tmb/3/238312/cd561f54bcb0957d9af82084598a89d8-800x.jpg "Б-деревья for(j=n(x)+1; j ≤ i; j--) Cj+1(x)= Cj(x); Ci+1[x]=z; for(j=n(x); j ≤")
