B-дерево

B-дерево (англ. B-tree) — сильноветвящееся сбалансированное дерево поиска, позволяющее проводить поиск, добавление и удаление элементов за [math]O(\log n)[/math]. B-дерево с [math]n[/math] узлами имеет высоту [math]O(\log n)[/math]. Количество детей узлов может быть от нескольких до тысяч (обычно степень ветвления B-дерева определяется характеристиками устройства (дисков), на котором производится работа с деревом). В-деревья также могут использоваться для реализации многих операций над динамическими множествами за время [math]O(\log n)[/math]

B-дерево было впервые предложено Р. Бэйером и Е. МакКрейтом в [math]1970[/math] году.

Структура

B-дерево является идеально сбалансированным, то есть глубина всех его листьев одинакова. B-дерево имеет следующие свойства ([math]t[/math] — параметр дерева, называемый минимальной степенью B-дерева, не меньший [math]2[/math].):

• Каждый узел, кроме корня, содержит не менее [math]t - 1[/math] ключей, и каждый внутренний узел имеет по меньшей мере [math]t[/math] дочерних узлов. Если дерево не является пустым, корень должен содержать как минимум один ключ.
• Каждый узел, кроме корня, содержит не более [math]2t - 1[/math] ключей и не более чем [math]2t[/math] сыновей во внутренних узлах
• Корень содержит от [math]1[/math] до [math]2t - 1[/math] ключей, если дерево не пусто и от [math]2[/math] до [math]2t[/math] детей при высоте большей [math]0[/math].
• Каждый узел дерева, кроме листьев, содержащий ключи [math]k_1, ..., k_n[/math], имеет [math]n + 1[/math] сына. [math]i[/math]-й сын содержит ключи из отрезка [math][k_{i - 1}; k_i],\: k_0 = -\infty,\: k_{n + 1} = \infty[/math].
• Ключи в каждом узле упорядочены по неубыванию.
• Все листья находятся на одном уровне.

Структура узла

struct Node
   bool leaf    // является ли узел листом
   int  n       // количество ключей узла
   int  key[]   // ключи узла
   Node c[]     // указатели на детей узла

Структура дерева

struct BTree
   int  t       // минимальная степень дерева
   Node root    // указатель на корень дерева

Назначение

B-деревья разработаны для использования на дисках (в файловых системах) или иных энергонезависимых носителях информации с прямым доступом, а также в базах данных. B-деревья похожи на красно-чёрные деревья (например, в том, что все В-деревья с [math]n[/math] узлами имеют высоту [math]O(\log n)[/math]), но они лучше минимизируют количество операций чтения-записи с диском.

Структуры данных во внешней памяти

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

Для того чтобы снизить время ожидания, связанное с механическим перемещением, при обращении к диску выполняется обращение одновременно сразу к нескольким элементам, хранящимся на диске. Информация разделяется на несколько страниц одинакового размера, которые хранятся последовательно друг за другом в пределах одного цилиндра (набора дорожек на дисках на одном расстоянии от центра), и каждая операция чтения или записи работает сразу с несколькими страницами. Для типичного диска размер страницы варьируется от [math]2[/math] до [math]16[/math] КБайт. После того, как головка установлена на нужную дорожку, а диск поворачивается так, что головка становится на начало интересующей нас страницы, чтение и запись становятся полностью электронными процессами, не зависящими от поворота диска, и диск может быстро читать или писать крупные объёмы данных.

В типичном приложении с B-деревом, объём хранимой информации так велик, что вся она просто не может храниться в основной памяти единовременно. Алгоритмы B-дерева копируют выбранные страницы с диска в основную память по мере надобности и записывает обратно на диск страницы, которые были изменены. Алгоритмы B-дерева хранят лишь определённое количество страниц в основной памяти в любой момент времени; таким образом, объём основной памяти не ограничивает размер B-деревьев, которые можно создавать.

Система в состоянии поддерживать в процессе работы в оперативной памяти только ограниченное количество страниц. Мы будем считать, что страницы, которые более не используются, удаляются из оперативной памяти системой; наши алгоритмы работы с В-деревьями не будут заниматься этим самостоятельно. Поскольку в большинстве систем время выполнения алгоритма, работающего с В-деревьями, зависит в первую очередь от количества выполняемых операций чтения/записи с диском, желательно минимизировать их количество и за один раз считывать и записывать как можно больше информации. Таким образом, размер узла В-дерева обычно соответствует дисковой странице. Количество потомков узла В-дерева, таким образом, ограничивается размером дисковой страницы. Для больших В-деревьев, хранящихся на диске, степень ветвления обычно находится между [math]50[/math] и [math]2000[/math], в зависимости от размера ключа относительно размера страницы. Большая степень ветвления резко снижает как высоту дерева, так и количество обращений к диску для поиска ключа. Например, если есть миллиард ключей, и [math]t=1001[/math], то поиск ключа займёт две дисковые операции.

Высота

Количество обращений к диску, необходимое для выполнения большинства операций с В-деревом, пропорционально его высоте. Проанализируем высоту В-дерева в наихудшем случае.

Теорема:

Если [math]n \geqslant 1[/math], то для B-дерева [math]T[/math] c [math]n[/math] узлами и минимальной степенью [math]t \geqslant 2[/math] имеется следующее неравенство: [math]h \leqslant[/math] [math]\log_t\dfrac{n+1}{2}[/math]

Доказательство:

[math]\triangleright[/math]

Корень B-дерева [math]T[/math] содержит по меньшей мере один ключ, а все остальные узлы — хотя бы [math]t - 1[/math] ключей. Так, [math]T[/math], высота которого [math]h[/math], имеет хотя бы [math]2[/math] узла на глубине [math]1[/math], хотя бы [math]2t[/math] узла на глубине [math]2[/math], хотя бы [math]2t^2[/math] узла на глубине [math]3[/math], и так далее, до глубины [math]h[/math], оно имеет по меньшей мере [math]2t^{h-1}[/math] узлов. Так, число ключей [math]n[/math] удовлетворяет неравенству: [math]n \geqslant 1+(t-1)\sum\limits_{i = 1}^h 2t^{i-1} [/math] [math]=1+2(t-1)(\dfrac{t^h-1}{t-1})[/math] [math]=2t^h-1[/math]. Простейшее преобразование дает нам неравенство [math]t^h \leqslant (n+1)/2[/math]. Логарифмирование по основанию [math]t[/math] обеих частей неравенства доказывает теорему

[math]\triangleleft[/math]

Здесь мы видим преимущества B-деревьев над красно-черными деревьями. Хотя высота деревьев растет как [math]O(\log t)[/math] в обоих случаях (вспомним, что [math]t[/math] — константа), в случае B-деревьев основание логарифмов имеет гораздо большее значение. Таким образом, В-деревья требуют исследования примерно в [math]\log t[/math] раз меньшего количества узлов по сравнению с красно-черными деревьями в большинстве операций. Поскольку исследование узла дерева обычно требует обращения к диску, количество дисковых операций при работе с В-деревьями оказывается существенно сниженным.

Операции

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

Поиск ключа

Если ключ содержится в текущем узле, возвращаем его. Иначе определяем интервал и переходим к соответствующему сыну. Повторяем пока ключ не найден или не дошли до листа.

Добавление ключа

Ищем лист, в который можно добавить ключ, совершая проход от корня к листьям. Если найденный узел незаполнен, добавляем в него ключ. Иначе разбиваем узел на два узла, в первый добавляем первые [math]t - 1[/math] ключей, во второй — последние [math]t - 1[/math] ключей. После добавляем ключ в один из этих узлов. Оставшийся средний элемент добавляется в родительский узел, где становится разделительной точкой для двух новых поддеревьев.

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

Вставка ключа в B-дерево [math]T[/math] высоты [math]h[/math] за один нисходящий проход по дереву потребует [math]O(h)[/math] обращений к диску и [math]O(th)=O(t \log_t n)[/math] процессорного времени.

void B-Tree-Insert(T: BTree, k: int):
    r = T.root
    if r.n == 2T.t - 1
        s = Allocate-Node()
        T.root = s
        s.leaf = false
        s.n = 0
        s.c[1] = r
        B-Tree-Split-Child(s, T.t, 1)
        B-Tree-Insert-Nonfull(s, k, T.t)
    else
        B-Tree-Insert-Nonfull(r, k, T.t)

void B-Tree-Insert-Nonfull(x: Node, k: int, t: int):
    i = x.n
    if x.leaf
        while i >= 1 and k < x.key[i]
            x.key[i+1] = x.key[i]
            i = i - 1
    x.key[i+1] = k
    x.n = x.n + 1
    Disk-Write(x)
    else 
        while i >= 1 and k < x.key[i]
            i = i - 1
        i = i + 1
        Disk-Read(x.c[i])
        if x.c[i].n == 2t - 1
            B-Tree-Split-Child(x, t, i)
            if k > x.key[i]
                i = i + 1
        B-Tree-Insert-Nonfull(x.c[i], k, t)

Функция [math]\operatorname{B-Tree-Insert-Nonfull}[/math] вставляет ключ [math]k[/math] в узел [math]x[/math], который должен быть незаполненным при вызове. Использование функции [math]\operatorname{B-Tree-Split-Child}[/math] гарантирует, что рекурсия не встретится с заполненным узлом. Ниже показана вставка ключей [math]B[/math], [math]Q[/math], [math]L[/math] и [math]F[/math] в дерево с [math]t = 3[/math], т.е. узлы могут содержать не более [math]5[/math] ключей

Разбиение узла

Функция [math]\operatorname{B-Tree-Split-Child}[/math] получает в качестве входного параметра незаполненный внутренний узел [math]x[/math] (находящийся в оперативной памяти), индекс [math]t[/math] и узел [math]y[/math] (также находящийся в оперативной памяти), такой что [math]y = c_i[x][/math] является заполненным дочерним узлом [math]x[/math]. Процедура разбивает дочерний узел на два и соответствующим образом обновляет поля [math]x[/math], внося в него информацию о новом дочернем узле. Для разбиения заполненного корневого узла мы сначала делаем корень дочерним узлом нового пустого корневого узла, после чего можно вызвать функцию. При этом высота дерева увеличивается на [math]1[/math]. Отметим, что увеличить высоту B-дерева можно только разбиением.

void B-Tree-Split-Child(x: Node, t: int, i: int):
    z = Allocate-Node()
    y = x.c[i]
    z.leaf = y.leaf
    z.n = t - 1
    for j = 1 to t - 1
        z.key[j] = y.key[j+t]
    if not y.leaf
        for j = 1 to t
            z.c[j] = y.c[j+t]
    y.n = t - 1
    for j = x.n + 1 to i + 1
        x.c[j+1] = x.c[j]
    x.c[i+1] = z
    for j = x.n to i
        x.key[j+1] = x.key[j]
    x.key[i] = y.key[t]
    x.n = x.n + 1
    Disk-Write(y)
    Disk-Write(z)
    Disk-Write(x)

Удаление ключа

Операция удаления ключа несколько сложнее, нежели добавление оного, так как необходимо убедиться, что удаляемый ключ находится во внутреннем узле. Процесс похож на поиск подходящего места для вставки ключа, с той разницей, что перед спуском в поддерево проверяется, достаточность количества ключей (т.е. [math]\geqslant t[/math]) в нем, а также возможность провести удаление, не нарушив структуры B-дерева. Таким образом, удаление аналогично вставке, и его проведение не потребует последующего восстановления структуры B-дерева. Если поддерево, выбранное поиском для спуска, содержит минимальное количество ключей [math]t-1[/math], производится либо перемещение, либо слияние. Удаление из листа и из внутреннего узла рассмотрено, а также операции слияния поддеревьев и перемещения ключей при удалении ключа рассмотрены ниже. Для удаления требуется время [math]O(t \log_t n)[/math] и [math]O(h)[/math] дисковых операций.

Удаление ключа из листа

Если удаление происходит из листа, смотрим на количество ключей в нем. Если ключей больше [math]t - 1[/math], то просто удаляем ключ.

В противном случае, если существует соседний лист с тем же родителем, который содержит больше [math]t - 1[/math] ключа, выберем ключ-разделитель из соседа разделяющий оставшиеся ключи соседа и ключи исходного узла (то есть не больше всех из одной группы и не меньше всех из другой). Обозначим этот ключ как [math]k_1[/math]. Выберем другой ключ из родительского узла, разделяющий исходный узел и его соседа, который был выбран ранее. Этот ключ обозначим [math]k_2[/math]. Удалим из исходного узла ключ, который нужно было удалить, спустим в этот узел [math]k_2[/math], а вместо [math]k_2[/math] в родительском узле поставим [math]k_1[/math]. Если все соседи содержат по [math]t - 1[/math] ключу, то объединяем узел с каким-либо из соседей, удаляем ключ, и ключ из родительского узла, который был разделителем разделённых соседей, переместим в новый узел.

Удаление ключа из внутреннего узла

Рассмотрим удаление из внутреннего узла. Имеется внутренний узел [math]x[/math] и ключ, который нужно удалить, [math]k[/math]. Если дочерний узел, предшествующий ключу [math]k[/math], содержит больше [math]t - 1[/math] ключа, то находим [math]k_1[/math] – предшественника [math]k[/math] в поддереве этого узла. Удаляем его. Заменяем [math]k[/math] в исходном узле на [math]k_1[/math]. Проделываем аналогичную работу, если дочерний узел, следующий за ключом [math]k[/math], имеет больше [math]t - 1[/math] ключа. Если оба (следующий и предшествующий дочерние узлы) имеют по [math]t - 1[/math] ключу, то объединяем этих детей, переносим в них [math]k[/math], а далее удаляем [math]k[/math] из нового узла. Если сливаются [math]2[/math] последних потомка корня – то они становятся корнем, а предыдущий корень освобождается.

Перемещение ключа

Если выбранное для нисходящего прохода поддерево содержит минимальное количеcтво ключей [math]t-1[/math], и предшествующие и следующие узлы-братья имеют по меньшей мере [math]t[/math] ключей, то ключ перемещается в выбранный узел. Поиск выбрал для спуска [math]x.c_2[/math] ([math]x.k_1\lt k_{delete}\lt x.k_2[/math]). Этот узел имеет лишь [math]t-1[/math] ключ (красная стрелка). Так как следующий брат [math]x.c_3[/math] содержит достаточное количество ключей, самый маленький ключ [math]x.c_3.k_1[/math] может перемещаться оттуда в родительский узел, чтобы переместить, в свою очередь, ключ [math]x.k_2[/math] как дополнительный ключ в выбранный для спуска узел. Левое поддерево [math]x.c_3.k_1[/math] — новое правое поддерево перемещённого ключа [math]x.k_2[/math].

Легко убедиться в том, что эти повороты поддерживают структуру B-дерева: для всех ключей [math]k[/math] на отложенном поддереве до и после перенесения выполняется условие [math]x.k_2 \leqslant k \leqslant x.c_3.k_1[/math]. Симметричная операция может производиться для перенесения ключа из предшествующего брата.

Слияние

Ниже будет рассмотрено слияние узлов при удалении ключей, то есть слияние узлов равной степени и высоты. Для произвольных же слияний потребуется приведение сливаемых деревьев к одной степени и высоте.

Итак, если выбранное для спуска поддерево [math]x.c_2[/math] и предшествующий и следующий узел-брат содержит минимальное количество ключей, то перемещение не возможно. На иллюстрации приводится слияние выбранного поддерева с предшествующим или следующим братом для такого случая. Для этого откладывается ключ из родительского узла [math]x[/math], который разделяет ключи на два сливаемых узла, в то время средний ключ перемещается в слитый узел. Ссылки на слитые дочерние узлы заменяются ссылкой на новый узел.

Так как алгоритм гарантирует, что узел, в который будет совершаться спуск, содержит по меньшей мере [math]t[/math] ключей вместо требуемых условиями B-дерева [math]t - 1[/math] ключей, родительский узел [math]x[/math] содержит достаточное количество ключей, чтобы выделить ключ для слияния. Это условие может быть нарушено, только в том случае, если два ребенка корня сливаются, так как поиск начинается с этого узла. По условиям B-дерева у корня должен быть как минимум один ключ, если дерево не пусто. При слиянии двух последних детей корня последний ключ перемещается во вновь возникшего единственного ребёнка, что приводит к пустому корневому узлу в не пустом дереве. В этом случае пустой узел корня удаляется и заменяется на единственного ребенка.

Вариации B-дерева

B+-дерево

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

B*-дерево

Распространённая модификация B-дерева, в которой каждый внутренний узел должен быть заполнен как минимум на две трети, а не наполовину, как в случае со стандартным B-деревом. Используется в файловых системах HFS и Reiser4. В отличие от B+-деревьев, узел не разбивается на [math]2[/math] узла, если полностью заполнен. Вместо этого ищется место в уже существующем соседнем узле, и только после того, как оба узла будут заполнены, они разделяются на три узла.

2-3 дерево

Производное от B+-дерева. Каждый узел может иметь либо [math]2[/math], либо [math]3[/math] ребёнка.

См. также

• 2-3 дерево
• B+-дерево
• Splay-дерево
• АВЛ-дерево
• Красно-черное дерево

Источники информации

• T. H. Cormen «Introduction to Algorithms» third edition, Chapter 18
• Т. Кормен «Алгоритмы: построение и анализ» второе издание, глава 18
• Д. Кнут «Искусство программирования. Сортировка и поиск», часть 6.2.4
• habrahabr.ru — B-tree
• Wikipedia — B-Baum
• Методы сортировки и поиска. Методы поиска во внешней памяти
• IBM. developerWorks. «Работа со структурами данных в языках Си и Python: Часть 10. B-деревья и TRIE-деревья»
• R. Bayer, E. McCreight «Organization and Maintenance of Large Ordered Indexes», Acta Informatica, 1972