B-дерево — различия между версиями

Версия 18:39, 12 июня 2012

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

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

Структура

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

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

Назначение

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

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

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

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

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

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

Высота

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

Теорема:

Если $n \geqslant 1$, то для B-дерева $T$ c $n$ узлами и минимальной степенью $t \geqslant 2$ имеется следующее неравенство:

$h \leqslant$ $\log_t\frac{n+1}{2}$

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

Корень B-дерева $T$ содержит по меньшей мере один ключ, а все остальные узлы — хотя бы $t - 1$ ключей. Так, T, высота которого $h$, имеет хотя бы $2$ узла на глубине $1$, хотя бы $2t$ узла на глубине $2$, хотя бы $2t^2$ узла на глубине $3$, и так далее, до глубины $h$, оно имеет по меньшей мере $2t^{h-1}$ узлов. Так, число ключей $n$ удовлетворяет неравенству:

$n \geqslant 1+(t-1)\sum\limits_{i = 1}^h 2t^{i-1} $

$=1+2(t-1)(\frac{t^h-1}{t-1})$

$=2t^h-1$.

Простейшее преобразование дает нам неравенство $t^h \leqslant (n+1)/2$. Логарифмирование по основанию $t$ обеих частей неравенства доказывает теорему

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

Операции

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

Поиск ключа

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

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

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

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

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

B-Tree-Insert-Nonfull(x, k)
    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, i)
            if k > x.key[i]
                i = i + 1
        B-Tree-Insert-Nonfull(x.c[i], k)

Функция $\operatorname{B-Tree-Insert-Nonfull}$ вставляет ключ $k$ в узел $x$, который должен быть незаполненным при вызове. Использование функции $\operatorname{B-Tree-Split-Child}$ гарантирует, что рекурсия не встретится с заполненным узлом.

</wikitex>

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

Разбиение узла B-дерева с t=4

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

B-Tree-Split-Child(x, i)
    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)

</wikitex>

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

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

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

Удаление из листа

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

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

Удаление из внутренних узлов

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

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

Перемещение ключа в B-дереве

Если выбранное для нисходящего прохода поддерево содержит минимальное количеcтво ключей $t-1$, и предшествующие и следующие узлы-братья имеют по меньшей мере $t$ ключей, то ключ перемещается в выбранный узел. Поиск выбрал для спуска $x.c_2$ ($x.k_1<k_{delete}<x.k_2$). Этот узел имеет лишь $t-1$ ключ (красная стрелка). Так как следующий брат $x.c_3$ содержит достаточное количество ключей, самый маленький ключ $x.c_3.k_1$ может перемещаться оттуда в родительский узел, чтобы перемещать, в свою очередь, ключ $x.k_2$ как дополнительный ключ в выбранный для спуска узел. Левое поддерево $x.c_3.k_1$ — новое правое поддерево перемещённого ключа $x.k_2$. Легко убедиться в том, что эти повороты поддерживают структуру B-дерева: для всех ключей $k$ на отложенном поддереве до и после перенесения выполняется условие $x.k_2 \leqslant k \leqslant x.c_3.k_1$. Симметричная операция может производиться для перенесения ключа из предшествующего брата.</wikitex>

Слияние

Слияние узла братом

Ниже будет рассмотрено слияние узлов при удалении ключей, то есть слияние узлов равной степени и высоты. Для произвольных же слияний потребуется приведение сливаемых деревьев к одной степени и высоте. Итак, если выбранное для спуска поддерево $x.c_2$ и предшествующий и следующий узел-брат содержит минимальное количество ключей, то перемещение не возможно. На иллюстрации приводится слияние выбранного поддерева с предшествующим или следующим братом для такого случая. Для этого откладывается ключ из родительского узла $x$, который разделяет ключи на два сливаемых узла, в то время средний ключ перемещается в слитый узел. Ссылки на слитые дочерние узлы заменяются ссылкой на новый узел. Так как алгоритм гарантирует, что узел, в который будет совершаться спуск, содержит по меньшей мере $t$ ключей вместо требуемых условиями B-дерева $t - 1$ ключей, родительский узел $x$ содержит достаточное количество ключей, чтобы выделить ключ для слияния. Это условие может быть нарушено, только в том случае, если два ребенка корня сливаются, так как поиск начинается с этого узла. По условиям B-дерева у корня должен быть как минимум один ключ, если дерево не пусто. При слиянии двух последних детей корня последний ключ перемещается во вновь возникшего единственного ребёнка, что приводит к пустому корневому узлу в не пустом дереве. В этом случае пустой узел корня удаляется и заменяется на единственного ребенка.</wikitex>

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

B+-дерево

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

B*-дерево

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

2-3 дерево

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

См.также

2-3 дерево

Ссылки

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

См. также