B-дерево

B-дерево

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

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

Структура

B-дерево является идеально сбалансированным, то есть глубина всех его листьев одинакова. <wikitex> Каждый узел B-дерева, кроме корня, содержит от $t - 1$ до $2t - 1$ ключей. Корень содержит от $1$ до $2t - 1$ ключей. $t$ — параметр дерева, не меньший $2$. Каждый внутренний узел, не являющийся корневым, имеет, таким образом, как минимум t дочерних узлов. Если дерево не является пустым, корень должен содержать как минимум один ключ. Ключи в каждом узле упорядочены. Мы говорим, что узел заполнен $(full)$, если он содержит ровно $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-деревья похожи на красно-чёрные деревья, но они лучше минимизируют количество операций чтения-записи в диске.

В типичном приложении с B-деревом, объём хранимой информации так велик, что вся она просто не может храниться в основной памяти единовременно. Алгоритмы B-дерева копируют выбранные страницы (мера информации на дисках; обычно, от $2^{11}$ до $2^{14}$ Байт) с диска в основную память по мере надобности и записывает обратно на диск страницы, которые были изменены. Алгоритмы B-дерева хранят лишь определённое количество страниц в основной памяти в любой момент времени; таким образом, объём основной памяти не ограничивает размер B-деревьев, которыми можно управлять.</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]

</wikitex>

Операции

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

Поиск ключа

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

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

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

Слияние

...

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

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

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

Ссылки

• T. H. Cormen «Introduction to Algorithms» third edition, Chapter 18
• Д. Кнут «Искусство программирования. Сортировка и поиск», часть 6.2.4
• Хабрахабр. B-tree.

См. также

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