B-дерево

/конспект в разработке/

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

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

Структура

B-дерево является идеально сбалансированным, то есть глубина всех его листьев одинакова. <wikitex> Каждый узел B-дерева, кроме корня, содержит от $t - 1$ до $2t - 1$ ключей. Корень содержит от $1$ до $2t - 1$ ключей. $t$ — параметр дерева, не меньший $2$. Каждый внутренний узел, не являющийся корневым, имеет, таким образом, как минимум t дочерних узлов. Если дерево не является пустым, корень должен содержать как минимум один ключ. Ключи в каждом узле упорядочены. Мы говорим, что узел заполнен, если он содержит ровно $2t-1$ ключей.</wikitex>

Каждый узел дерева, кроме листьев, содержащий ключи [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].

Назначение

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

Использование во вторичной памяти

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

Хотя диски существенно дешевле оперативной памяти и имеют высокую емкость, они гораздо, гораздо медленнее оперативной памяти. Механическое движение головки относительно диска определяется двумя компонентами — перемещением головки по радиусу и вращением дисков. При скорости вращения 7200 оборотов в минуту один оборот требует примерно 8.33 мс, что почти на 5 порядков превышает время обращения к оперативной памяти (которое составляет примерно 100 нс). То есть, пока мы ждем оборота диска, чтобы считать необходимые нам данные, из оперативной памяти мы могли бы получить эти данные почти 100000 раз. В среднем приходится ждать только половину оборота диска, но это практически ничего не меняет. Радиальное перемещение головок тоже требует времени. Для того чтобы снизить время ожидания, связанное с механическим перемещением, при обращении к диску выполняется обращение одновременно сразу к нескольким элементам, хранящимся на диске. Информация разделяется на несколько страниц (pages) одинакового размера, которые хранятся последовательно друг за другом в пределах одного цилиндра (набора дорожек на дисках на одном расстоянии от центра), и каждая операция чтения или записи работает сразу с несколькими страницами. Для типичного диска размер страницы варьируется от $2^{11}$ до $2^{14}$ Байт. После того, как головка позиционирована на нужную дорожку, а диск поворачивается так, что головка становится на начало интересующей нас страницы, чтение/запись становится полностью электронным процессами, не зависящими от поворота диска, и диск может быстро читать или писать крупные объёмы данных.

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

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

Высота

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

Теорема:

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Здесь мы видим преимущества 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(tlog_g 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 $\geqslant$ 1) && (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 $\geqslant$ 1) && (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)
    }
}

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

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

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

<wikitex>Функция B-Tree-Split-Child получает в качестве входного параметра незаполненный внутренний узел $x$ (находящийся в оперативной памяти), индекс $t$ и узел $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 downto i + 1
        x.$C_{j+1}$ = x.$C_j$
    $x.c_{i+1}$ = z
    for j = x.n downto 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>

Слияние

...

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

Находим ключ, который необходимо удалить

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

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

B+-дерево

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

B*-дерево

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

2-3 дерево

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

См.также

• 2-3 дерево

Ссылки

• T. H. Cormen «Introduction to Algorithms» third edition, Chapter 18
• Т. Кормен «Алгоритмы: построение и анализ» второе издание, глава 18
• Д. Кнут «Искусство программирования. Сортировка и поиск», часть 6.2.4
• Хабрахабр. B-tree.
• Методы сортировки и поиска. Методы поиска во внешней памяти

См. также

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