B-деревья

 До сих пор мы рассматривали только бинарные деревья. Теперь рассмотрим деревья, имеющие бОльшую степень ветвления. При этом хочется, чтобы сохранялись свойства, аналогичные свойству сбалансированности в сбалансированных деревьях. Этим условиям удовлетворяют B-деревья. Отметим, что B-деревья являются основным инструментом построения многих современных файловых систем (NTFS, RaiserFS, JFS, XFS).

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

В-дерево степени n определяется следующим образом

·      каждая вершина дерева, кроме корня, содержит от n-1 до 2n-1 элемента (ключей) и от n до 2n ссылок на дочерние элементы; корень дерева содержит не более 2n-1 элементов (ключей) и не более 2n ссылок на дочерние элементы

·      В-дерево идеально сбалансировано, более того, длины всех ветвей от корня до листа совпадают;

·      элементы в каждой вершине упорядочены по возрастанию

·      если в вершине содержится k элементов, то в ней содержится k+1 ссылок на дочерние вершины (кроме листьев, ссылок на дочерние вершины не содержащих);

·      элементы в вершине и ссылки на дочерние вершины сопоставляются следующим образом: про первую ссылку говорят, что она располагается до первого элемента, про последнюю – что она располагается после последнего элемента, остальные ссылки располагаются каждая – между некоторой парой элементов в вершине;

·      все элементы xi в поддереве V, ссылка на которое расположена после некоторого элемента y, больше y; все элементы xj в поддереве V, ссылка на которое расположена до некоторого элемента z меньше z.

Пример В-дерева степени 3:

 

Как правило, В-деревья имеют достаточно большие степени. Например, их задают исходя из того, что одна вершина должна занимать один блок на диске.

На языке С тип данных для хранения одной вершины В-дерева степени 100 целых чисел можно определить следующим образом

#define NB 100

typedef struct BNode_

{

 struct BNode_ *par;

 int n;

 struct BNode_ *child[2*NB];

 int value[2*NB];

} BNode;

Здесь n – количество элементов, содержащихся в вершине, value[i] – значение i-го элемента, child[i] – указатель на соответствующего потомка. Заметим, что мы отвели на один целый элемент больше, чем нам требуется для хранения данных. Этим мы воспользуемся позднее – при поиске элемента в В-дереве.

Если элемент дерева занимает много места, то имеет смысл в вершинах хранить не сами данные, а указатели на них. Так, например, допустим, мы хотим создать дерево для хранения строк, в понимании языка С, тогда тип вершины можно определить следующим образом

#define NB 100

typedef struct BNode_

{

 struct BNode_ *par;

 int n;

 struct BNode_ *child[2*NB];

 char  *str[2*NB-1];

} BNode;

 

Инициализировать такую структуру можно очень простой функцией:

void Init(BNode *node){memset(node,0,sizeof(BNode));}

После инициализации занесение строки в k-ый элемент вершины можно осуществить следующей функцией

void Insert(BNode *node, int i_elem, char *str)

{

 if(node->str[i_elem]!=NULL)free(node->str[i_elem]);

 node->str[i_elem]=strdup(str);

}

 

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

Получим оценку на высоту В-дерева через количество элементов в нем.

Корень дерева содержит не менее одного элемента. На втором уровне содержится не менее двух вершин, а в каждой вершине – не менее n-1 элементов. На каждом следующем уровне количество вершин увеличивается не менее чем в n раз (т.к. каждая вершина имеет не менее n потомков). Т.о. на k-ом уровне будет не менее  2nk-2 вершин для k>1, и, соответственно, не менее  2(n-1)nk-2 элементов.

Т.о. получаем оценку на количество элементов N в дереве высоты h

N ³ 1+Sk=2k£h 2(n-1)nk-2=1+2(n-1)Sk=0k£h-2 nk=

=1+2(n-1)(nh-1-1)/(n-1)= 2 nh-1-1

Т.о., учитывая то, что оценка сверху на число элементов в дереве получается аналогичным образом, мы получаем, что верна следующая

Теорема. Для В-дерева степени n, содержащего N элементов, высоты h верна оценка для высоты

h=Q(lognN).

Верна точная оценка

h £ logn((N+1)/2)+1.

Поиск вершины в B-дереве

Поиск вершины, содержащей заданный элемент (или элемент с ключом, равным заданному), осуществляется аналогично поиску в двоичном дереве поиска. Единственное отличие – для каждой вершины процедура поиска данного элемента более сложная, чем для случая дерева поиска. На языке С поиск элемента, равного v, в В-дереве с корнем root можно оформить в виде следующей функции

BNode *BSearch(BNode *root, int v)

{

  if(root==NULL)return NULL;

  for(i=0;i<root->n;i++)

   if(root->value[i]==v)return root;

   else if(root->value[i]>v)return BSearch(root->child[i],v);

 return BSearch(root->child[i],v);

}

Отступление на тему языка С. Быстрый поиск и сортировка в языке С

В конкретных реализациях степень В-дерева может быть весьма большой. Поэтому поиск элемента в одной вершине при больших степенях В-деревьев следует производить с помощью двоичного поиска. В языке С есть стандартная функция для поиска в упорядоченном массиве bsearch. Например, в Microsoft Visual C эта функция имеет следующее описание

void *bsearch( const void *key, const void *base, size_t nmemb, size_t size, int ( __cdecl *compare ) ( const void *elem1, const void *elem2 ) );

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

void *bsearch(const void *key, const void *base, size_t nmemb, size_t size, int (*compare)(const void * elem1, const void * elem2));

Здесь key – указатель на искомый элемент, base – указатель на массив с данными, nmemb – количество элементов в массиве, size – размер в байтах одного элемента массива, compare – указатель на функцию, получающую указатель на два элемента массива и возвращающую результат сравнения элементов: +1 – если первый элемент больше второго, -1 – если второй элемент больше первого, 0 – если элементы равны.

Для нашего случая – поиска целого числа в массиве функция сравнения может быть определена следующим образом

int compare(const void *v0,const void *v1)

{ return *(int*)v0>*(int*)v1 ? 1 : *(int*)v0<*(int*)v1 ? -1 : 0 ; }

 

К сожалению, если данный элемент в массиве не найдет, то функция bsearch возвращает NULL, при этом информация о том – между какими элементами находится искомый, теряется. Если нам все же хочется непременно воспользоваться функцией bsearch, то мы можем применить некоторый трюк: мы можем воспользоваться информацией о том, что реально – первый параметр bsearch это – адрес искомого элемента, а второй – адрес некоторого элемента в массиве. Исходя из алгоритма двоичной сортировки, если искомый элемент в массиве отсутствует, то последний элемент *v1 при вызове функции compare, для которого оказалось, что

*(int*)v0<*(int*)v1

будет ближайшим элементом массива, большим искомого (=*(int*)v0) . Адрес этого элемента можно запомнить в соответствующей глобальной переменной. Чтобы указанное свойство было верным и для последнего элемента исходного массива, поместим вслед за последним элементом массива самое большое из всех чисел типа int, и, соответственно, запретим его использование в обычной работе. Поиск же элемента будем производить в расширенном массиве. В этом случае функцию сравнения следует оформить следующим образом

int *v_gt_save=NULL;

int compare (const void *v0,const void *v1)

{

 if(*(int*)v0>*(int*)v1)return 1;

 if(*(int*)v0<*(int*)v1){v_gt_save=(int*)v1;return -1;}

 return 0;

}

 

Функция поиска вершины может тогда выглядеть следующим образом

 

BNode *BSearchQ(BNode *root, int v)

{

  if(root==NULL)return NULL;

  root->value[root->n]= INT_MAX;

  if(bsearch(&v, root->value, root->n+1, sizeof(int),compare))return root;

  return BSearchQ(root->child[v_gt_save-root->value], v);

}

Здесь константа INT_MAX обозначает максимальное число типа int. Данная константа (определяемая через #define) является, фактически, стандартной в разных версиях языка С. Так, например, в Microsoft Visual C и GCC эта константа определяются в стандартном файле include.h.

Отметим, что данный подход, возможно, не является оптимальным как в плане скорости счета (присутствует лишняя операция присваивания v_gt_save=(int*)v1), так и в плане выполнения правил хорошего тона (в алгоритме использовались глобальные переменные). Однако этот подход немного экономит время программиста (не надо программировать алгоритм двоичного поиска). В нашем же случае он, скорее, служит примером использования функции bsearch.

Еще одним примером использования указателей на функцию является использование функции быстрой сортировки. Функция имеет следующее описание в Microsoft Visual C

void qsort( void *base, size_t num, size_t size, int (__cdecl *compare )(const void *elem1, const void *elem2 ) );

а в GCC:

void qsort(void *base, size_t num, size_t size, int (*compar)(const void*,const void*));

здесь base – указатель на массив с данными, num – количество элементов в массиве, size – размер в байтах одного элемента массива, compare – указатель на функцию, получающую указатель на два элемента массива и возвращающую результат сравнения элементов: +1 – если первый элемент больше второго, -1 – если второй элемент больше первого, 0 – если элементы равны.

Например, в нашем случае отсортировать массив элементов одной вершины node В-дерева можно следующим образом

Bnode *node;

qsort(node->value, node->n, sizeof(int),compare);

Добавление вершины в B-дерево в два прохода

1.      По аналогии с деревом поиска сначала ищется лист, в который можно вставить новый элемент (это – первый проход по дереву).

2.      Заметим, что листом дерева называется элемент без потомков. Если найденный лист V не заполнен, то новый элемент вставляется в лист V В-дерева степени n и на этом процедура завершается.

3.      Иначе в элементах данной вершины находится медиана x и вершина разбивается на две вершины по n-1 элементу в каждой, причем элементы в первой вершине V-  должны быть меньше x, а во второй V+  – больше x.

4.      Элемент x вставляется в массив элементов в родительской вершине между элементами, между которыми находилась ссылка на вершину V. Ссылки на вершины V-  и V+ должны расположиться непосредственно слева и справа от x.

5.      Теперь новый элемент можно вставить в одну из вершин V-  или V+.

6.      После этого, если в родительской вершине количество элементов становится меньше 2n-1, то на этом процедура завершается. Иначе процедура разбиения вершины рекурсивно применяется для родителя (т.е. переходим к шагам 3, 4, 6). В этом заключается второй проход по дереву.

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

 

Приведем пример. В следующее B-дерево степени 3 требуется вставить элемент со значением 4.

 

Элемент 4 надо вставлять в вершину со значениями {1, 2, 5, 7, 8}. Вершина заполнена, поэтому мы разбиваем ее на две вершины {1, 2} и {7, 8} и медиану 5. Родительская вершина не заполнена, поэтому мы вставляем ключ 5 в родительскую вершину (с заменой ссылки на старый лист на ссылки на два новых листа):

 

Осталось вставить элемент 4 в лист {1, 2}:

 

 

Добавление вершины в B-дерево за один проход

Не составляет труда выполнить процедуру вставки нового элемента в B-дерево степени n за один проход. Для этого сначала проверяется – заполнен ли корень дерева. Если корень заполнен, то он разбивается на две новые вершины, состоящие из первых и последних n-1 элемента, и создается новый корень дерева, в который добавляется медиана старого корня со ссылками на две новые вершины. Далее при поиске требуемого листа следует для каждой пройденной вершины (включая лист) проверять – заполнена ли она. Если вершина заполнена, то (по аналогии с корнем дерева) ее следует разбить на две вершины, состоящие из первых и последних n-1 элемента, и вставить медиану элементов из данной вершины в вышестоящую вершину. При этом ссылка на данную вершину (от родителя) заменяется на две ссылки на новые вершины (слева и справа от вставленного значения). Данная вставка не приведет к переполнению родительской вершины, т.к. на предыдущем шаге было обеспечено, что родительская вершина не заполнена.  

 

Удаление вершины из B-дерева за один проход

 

Для удаления элемента, равного заданному, требуется, сначала, его найти. При осуществлении поиска мы параллельно будем обеспечивать условие, гарантирующее, чтобы в вершине, из которой будет удаляться элемент, было бы не менее n элементов (по определению В-дерева достаточно, чтобы в вершине присутствовало не менее n-1 элемента).

Итак, в процессе поиска вершины, содержащей удаляемый элемент v, мы вводим понятие текущей вершины x. Текущая вершина перемещается от корня дерева по соответствующей ветви к вершине, содержащей удаляемый элемент.

Для каждого очередного значения текущей вершины возможен один из следующих вариантов

 

1) Вершина является листом.

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

 

2) Вершина x - внутренняя. Элемент v в вершине x не найден.

Ищем потомка x->child[i] вершины x, с которого начинается поддерево,

содержащее элемент v (если он вообще есть в дереве). По условию мы должны гарантировать, чтобы в вершине x->child[i] содержалось бы не менее n элементов. Если это выполняется, то переходим к рассмотрению этой вершины:

x=x->child[i].

Иначе мы либо `перетаскиваем' один элемент из брата вершины x->child[i] в

вершину x->child[i], либо, если это невозможно, объединяем данную вершину с братом. Более подробно, есть два варианта:

   а) У вершины x->child[i] есть брат, содержащий не менее n элементов.

   Пусть, для определенности, это - правый брат, т.е.  x->child[i+1]->n ³ n.

   Тогда мы переносим элемент x->value[i] в конец массива элементов x->child[i]

   (соответственно, увеличив на 1 значение x->child[i]->n) и

   элемент x->child[i+1]->value[0] переносим на место x->value[i]

   (соответственно, уменьшив на 1 значение c->child[i+1]->n):

 

   x->child[i]->value[++x->child[i]->n]=x->value[i];

   x->value[i]=x->child[i+1]->value[0];

   for(i=1;i<x->child[i+1]->n;i++)

     x->child[i+1]->valuie[i-1]=x->child[i+1]->valuie[i];

   x->child[i+1]->n--;

 

Например, требуется в следующем дереве удалить вершину 11 в В-дереве степени 3:

У данной вершины есть сосед (левый), содержащий 3 элемента. Тогда мы максимальный элемент из этой вершины – 7 – помещаем на место 10, а 10 помещаем на место 11:





 

  
 

 

  
  
 




 

 


 

   Теперь мы можем перейти к рассмотрению следующей вершины:

   x=x->child[i];

 

   б) У вершины x->child[i] все братья содержат n-1 элемент.

Допустим,  для определенности, у вершины x->child[i] есть правый брат. Тогда, мы объединяем вершину x->child[i] с вершиной x->child[i+1] с помощью стыковочного элемента x->value[i]. Т.е. мы добавляем элемент x->value[i] в конец массива x->child[i]->value и затем добавляем все элементы из   x->child[i+1] в конец массива x->child[i]->value.

Осталось удалить все лишнее: элемент x->value[i] из массива  x->value, потомка    x->child[i+1], ссылку x->child[i+1] из массива x->child.

Здесь мы воспользовались тем, что в вершине x есть хотя бы n элементов, либо она является корнем. В последнем случае если в корне есть всего лишь один элемент, то старая вершина с корнем уничтожается, а два потомка корня, содержащие ранее по n-1 элементу вместе со ключом из старого корня образуют новый корень, состоящий из 2n-1 элемента.

 

Например, требуется в следующем дереве удалить вершину 14 в В-дереве степени 3:

 

 

Для этого мы объединяем вершину {11,14} с элементом 15 и с вершиной {17,57}:

 

 

 


 

 

    Теперь мы можем перейти к рассмотрению следующей вершины:

    x=x->child[i];

 

3. Вершина x - внутренняя, в вершине найден элемент x->value[i]==v.

Сначала удаление производится аналогично дереву поиска: в одном из поддеревьев, соседних данной вершине, например, для определенности, в правом соседнем поддереве данной вершины (т.е. в поддереве, начинающемся с вершины                       x->child[i+1]) находим элемент v0, ближайший к v. В нашем случае это – минимальный элемент поддерева, начинающегося с вершины x->child[i+1]. Заметим, что минимальный элемент в поддереве B-дерева является первым элементом некоторого листа.

Далее, помещаем элемент v0 на  место элемента v и запускаем процедуру удаления старого (т.е. удаленного) элемента v0.

Здесь, чтобы не запутаться в `старом’ v0 и `новом’ v0 лучше сначала запомнить адрес элемента, на который мы должны скопировать v0  и само значение v0, далее можно осуществить процедуру удаления элемента v0 и только потом скопировать запомненное v0 по запомненному адресу. 

 

 

B+-деревья

            Интересной и очень важной модификацией B-деревьев являются B+-деревья. Приведем далее формальное определение B+-дерева, выделив заглавными буквами формальные отличие между B-деревьями и B+-деревья.

B+-дерево степени n определяется следующим образом

·      каждая вершина дерева, кроме корня, содержит от n-1 до 2n-1 элемента (ключей) и от n до 2n ссылок на дочерние элементы; корень дерева содержит не более 2n-1 элементов (ключей) и не более 2n ссылок на дочерние элементы

·      В-дерево идеально сбалансировано, более того, длины всех ветвей совпадают;

·      элементы в каждой вершине упорядочены по возрастанию

·      если в вершине содержится k элементов, то в ней содержится k+1 ссылок на дочерние вершины (кроме листьев, ссылок на дочерние вершины не содержащих);

·      элементы в вершине и ссылки на дочерние вершины сопоставляются следующим образом: про первую ссылку говорят, что она располагается до первого элемента, про последнюю – что она располагается после последнего элемента, остальные ссылки располагаются каждая – между некоторой парой элементов в вершине;

·      все элементы xi в поддереве V, ссылка на которое расположена после некоторого элемента y, БОЛЬШЕ ИЛИ РАВНЫ y; все элементы xj в поддереве V, ссылка на которое расположена до некоторого элемента z меньше z.

·      ССЫЛКИ НА ДАННЫЕ ЛЕЖАТ ТОЛЬКО НА НИЖНЕМ УРОВНЕ ДЕРЕВА (В ЛИСТЬЯХ); ВО ВСЕХ ОСТАЛЬНЫХ ВЕРШИНАХ ЛЕЖАТ ТОЛЬКО КОПИИ КЛЮЧЕЙ ЭЛЕМЕНТОВ С НИЖНЕГО УРОВНЯ, ИСПОЛЬЗУЮЩИЕСЯ ДЛЯ ИНДЕКСИРОВАНИЯ.

           

            Пример B+-дерева степени 3:

            Основным преимуществом данной структуры данных является то, что все реальные ключи данных, содержащихся в дереве, лежат на одном уровне (на нижнем). Поэтому не сложно завязать эти элементы в список, что существенно упрощает процедуру последовательно перебора данных их списка. Например, именно B+-деревья используются во всех прогрессивных файловых системах (NTFS, RaiserFS, XFS и т.д.).

Поиск вершины в B+-дереве

Поиск вершины, содержащей ссылку на заданный элемент, осуществляется аналогично поиску в B-дереве, с той лишь разницей, что искать надо в любом случае вплоть до листа. На языке С поиск элемента, равного v, в В+-дереве с корнем root можно оформить в виде следующей функции

BNode *BSearch(BNode *root, int v)

{

  if(root==NULL)return NULL;

  if(root->child[0]==NULL)//если мы работает с листом

 {

   for(i=0;i<root->n;i++) if(root->value[i]==v)return root;

   return NULL;

 }

 for(i=0;i<root->n;i++) if(root->value[i]>v)return BSearch(root->child[i],v);

 return BSearch(root->child[root->n],v);

}

Добавление вершины в B+-дерево в два прохода

Вставка нового элемента в B+-дерево делается аналогично вставке элемента в B-дерево, но случай заполнения вершины до 2n-1 элементов обрабатывается немного по-другому:

·         Вершина P (лист), в которой образуется 2n-1 элемент, разбивается на две вершины P1 и P2 с, соответственно, n и n-1 элементами;

·         Ссылка на P заменяется на ссылку на P1;

·         Пара (Ключ минимального элемента из P2, ссылка на P2) вставляется в родителя данной вершины после ссылки на P1;

·         Если после этого родительская вершина оказывается заполненной, то с ней рекурсивно осуществляется аналогичная процедура.

Удаление вершины из B+-дерева

 

            Удаление элемента из B+-дерева делается аналогично удалению элемента из B-дерева, но оно требует аккуратной корректировки индексов в родительских вершинах.