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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Удаление ключа)
м (rollbackEdits.php mass rollback)
 
(не показано 146 промежуточных версий 10 участников)
Строка 1: Строка 1:
'''B-дерево''' дерево поиска, позволяющее проводить поиск, добавление и удаление элементов за <tex>O(\log n)</tex>.
+
'''B-дерево''' (англ. ''B-tree'') {{---}} сильноветвящееся сбалансированное дерево поиска, позволяющее проводить поиск, добавление и удаление элементов за <tex>O(\log n)</tex>. B-дерево с <tex>n</tex> узлами имеет высоту <tex>O(\log n)</tex>. Количество детей узлов может быть от нескольких до тысяч (обычно степень ветвления B-дерева определяется характеристиками устройства (дисков), на котором производится работа с деревом). В-деревья также могут использоваться для реализации многих операций над динамическими множествами за время <tex>O(\log n)</tex>
  
B-дерево было впервые предложено Р. Бэйером и Е. МакКрейтом в 1970 году.
+
B-дерево было впервые предложено Р. Бэйером и Е. МакКрейтом в <tex>1970</tex> году.
 +
== Структура ==
 +
B-дерево является идеально сбалансированным, то есть глубина всех его листьев одинакова.
 +
B-дерево имеет следующие свойства (<tex>t</tex> — параметр дерева, называемый ''минимальной степенью'' B-дерева, не меньший <tex>2</tex>.):
 +
* Каждый узел, кроме корня, содержит не менее <tex>t - 1</tex> ключей, и каждый внутренний узел имеет по меньшей мере <tex>t</tex> дочерних узлов. Если дерево не является пустым, корень должен содержать как минимум один ключ.
 +
* Каждый узел, кроме корня, содержит не более <tex>2t - 1</tex> ключей и не более чем <tex>2t</tex> сыновей во внутренних узлах
 +
* Корень содержит от <tex>1</tex> до <tex>2t - 1</tex> ключей, если дерево не пусто и от <tex>2</tex> до <tex>2t</tex> детей при высоте большей <tex>0</tex>.
 +
* Каждый узел дерева, кроме листьев, содержащий ключи <tex>k_1, ..., k_n</tex>, имеет <tex>n + 1</tex> сына. <tex>i</tex>-й сын содержит ключи из отрезка <tex>[k_{i - 1}; k_i],\:  k_0 = -\infty,\: k_{n + 1} = \infty</tex>.
 +
* Ключи в каждом узле упорядочены по неубыванию.
 +
* Все листья находятся на одном уровне.
  
== Структура ==
+
=== Структура узла ===
 +
'''struct''' Node
 +
    '''bool''' leaf <span style="color:#008000">  // является ли узел листом</span>
 +
    '''int'''  n <span style="color:#008000">      // количество ключей узла</span>
 +
    '''int'''  key[] <span style="color:#008000">  // ключи узла</span>
 +
    '''Node''' c[] <span style="color:#008000">    // указатели на детей узла</span>
 +
=== Структура дерева ===
 +
'''struct''' BTree
 +
    '''int'''  t <span style="color:#008000">      // минимальная степень дерева</span>
 +
    '''Node''' root <span style="color:#008000">  // указатель на корень дерева</span>
  
B-дерево является идеально сбалансированным, то есть глубина всех его листьев одинакова.
+
== Назначение ==
 +
B-деревья разработаны для использования на дисках (в файловых системах) или иных энергонезависимых носителях информации с прямым доступом, а также в базах данных. B-деревья похожи на красно-чёрные деревья (например, в том, что все В-деревья с <tex>n</tex> узлами имеют  высоту <tex>O(\log n)</tex>), но они лучше минимизируют количество операций чтения-записи с диском.
 +
== Структуры данных во внешней памяти ==
 +
Кроме оперативной памяти, в компьютере используется внешний носитель, как правило, представляющий собой магнитные диски (или твердотельный накопитель). Хотя диски существенно дешевле оперативной памяти и имеют высокую емкость, они гораздо медленнее оперативной памяти из-за механического построения считывания.
  
Каждый узел B-дерева, кроме корня, содержит от <tex>t - 1</tex> до <tex>2t - 1</tex> ключей. Корень содержит от <tex>1</tex> до <tex>2t - 1</tex> ключей. <tex>t</tex> — параметр дерева, не меньший <tex>2</tex>. Ключи в каждом узле упорядочены.
+
Для того чтобы снизить время ожидания, связанное с механическим перемещением, при обращении к диску выполняется обращение одновременно сразу к нескольким элементам, хранящимся на диске. Информация разделяется на несколько страниц одинакового размера, которые хранятся последовательно друг за другом в пределах одного цилиндра (набора дорожек на дисках на одном расстоянии от центра), и каждая операция чтения или записи работает сразу с несколькими страницами. Для типичного диска размер страницы варьируется  от <tex>2</tex> до <tex>16</tex> КБайт. После того, как головка установлена на нужную дорожку, а диск поворачивается так, что головка становится на начало интересующей нас страницы, чтение и запись становятся полностью электронными процессами, не зависящими от поворота диска, и диск может быстро читать или писать крупные объёмы данных.
  
Каждый узел дерева, кроме листьев, содержащий ключи <tex>k_1, ..., k_n</tex>, имеет <tex>n + 1</tex> сына. <tex>i</tex>-й сын содержит ключи из интервала <tex>(k_{i - 1}; k_i), k_0 = -\infty, k_{n + 1} = \infty</tex>.
+
В типичном приложении с B-деревом, объём хранимой информации так велик, что вся она просто не может храниться в основной памяти единовременно. Алгоритмы B-дерева копируют выбранные страницы с диска в основную память по мере надобности и записывает обратно на диск страницы, которые были изменены. Алгоритмы B-дерева хранят лишь определённое количество страниц в основной памяти в любой момент времени; таким образом, объём основной памяти не ограничивает размер B-деревьев, которые можно создавать.
  
== Назначение ==
+
Система в состоянии поддерживать в процессе работы в оперативной памяти только ограниченное количество страниц. Мы будем считать, что страницы, которые более не используются, удаляются из оперативной памяти системой; наши алгоритмы работы с В-деревьями не будут заниматься этим самостоятельно. Поскольку в большинстве систем время выполнения алгоритма, работающего с В-деревьями, зависит в первую очередь от количества выполняемых операций чтения/записи с диском, желательно минимизировать их количество и за один раз считывать и записывать как можно больше информации. Таким образом, размер узла В-дерева обычно соответствует дисковой странице. Количество потомков узла В-дерева, таким образом, ограничивается размером дисковой страницы.
 +
Для больших В-деревьев, хранящихся на диске, степень ветвления обычно находится между <tex>50</tex> и <tex>2000</tex>, в зависимости от размера ключа относительно размера страницы. Большая степень ветвления резко снижает как высоту дерева, так и количество обращений к диску для поиска ключа. Например, если есть миллиард ключей, и <tex>t=1001</tex>, то поиск ключа займёт две дисковые операции.
  
B-деревья используются для хранения информации на жёстком диске. Время произвольного доступа к жёсткому диску очень велико, поэтому важно уменьшить количество узлов, просматриваемых при каждой операции, то есть высоту дерева, что достигается путём высокой ветвистости.
+
== Высота ==
 +
Количество обращений к диску, необходимое для выполнения большинства операций с В-деревом, пропорционально его высоте. Проанализируем высоту В-дерева в наихудшем случае.
 +
{{Теорема|statement=Если <tex>n \geqslant 1</tex>, то для B-дерева <tex>T</tex> c <tex>n</tex> узлами и минимальной степенью <tex>t \geqslant 2</tex> имеется следующее неравенство:
 +
:<tex>h \leqslant</tex> <tex>\log_t\dfrac{n+1}{2}</tex>
 +
|proof=
 +
Корень B-дерева <tex>T</tex> содержит по меньшей мере один ключ, а все остальные узлы — хотя бы <tex>t - 1</tex> ключей. Так, <tex>T</tex>, высота которого <tex>h</tex>, имеет хотя бы <tex>2</tex> узла на глубине <tex>1</tex>, хотя бы <tex>2t</tex> узла на глубине <tex>2</tex>, хотя бы <tex>2t^2</tex> узла на глубине <tex>3</tex>, и так далее, до глубины <tex>h</tex>, оно имеет по меньшей мере <tex>2t^{h-1}</tex> узлов. Так, число ключей <tex>n</tex> удовлетворяет неравенству:
 +
::<tex>n \geqslant 1+(t-1)\sum\limits_{i = 1}^h 2t^{i-1} </tex>
 +
:::<tex>=1+2(t-1)(\dfrac{t^h-1}{t-1})</tex>
 +
:::<tex>=2t^h-1</tex>.
  
== Поиск ключа ==
+
Простейшее преобразование дает нам неравенство <tex>t^h \leqslant (n+1)/2</tex>. Логарифмирование по основанию <tex>t</tex> обеих частей неравенства доказывает теорему
 +
}}
  
 +
Здесь мы видим преимущества B-деревьев над красно-черными деревьями. Хотя высота деревьев растет как <tex>O(\log t)</tex> в обоих случаях (вспомним, что <tex>t</tex> — константа), в случае B-деревьев основание логарифмов имеет гораздо большее значение. Таким образом, В-деревья требуют исследования примерно в <tex>\log t</tex> раз меньшего количества узлов по сравнению с красно-черными деревьями в большинстве операций. Поскольку исследование узла дерева обычно требует обращения к диску, количество дисковых операций при работе с В-деревьями оказывается существенно сниженным.
 +
== Операции ==
 +
B-деревья представляют собой сбалансированные деревья, поэтому время выполнения стандартных операций в них пропорционально высоте. Однако, как уже было упомянуто выше, алгоритмы B-дерева созданы специально для работы с дисками (или другими носителями информации) и базами данных (или иными видами представления большого количества информация), минимизируя количество операций ввода-вывода.
 +
=== Поиск ключа ===
 
Если ключ содержится в текущем узле, возвращаем его. Иначе определяем интервал и переходим к соответствующему сыну. Повторяем пока ключ не найден или не дошли до листа.
 
Если ключ содержится в текущем узле, возвращаем его. Иначе определяем интервал и переходим к соответствующему сыну. Повторяем пока ключ не найден или не дошли до листа.
 +
=== Добавление ключа ===
 +
Ищем лист, в который можно добавить ключ, совершая проход от корня к листьям. Если найденный узел незаполнен, добавляем в него ключ. Иначе разбиваем узел на два узла, в первый добавляем первые <tex>t - 1</tex> ключей, во второй — последние <tex>t - 1</tex> ключей. После добавляем ключ в один из этих узлов. Оставшийся средний элемент добавляется в родительский узел, где становится разделительной точкой для двух новых поддеревьев.
 +
[[Файл:B3inssp.png|550px|Разбиение корня с t = 4. Корневой узел r разделяется на два узла, и создаётся новый корень s. Новый корень содержит средний ключ r и две половины r в качестве детей. Разбиением узла высота дерева увеличивается на единицу]]
 +
 +
Если и родительский узел заполнен — повторяем пока не встретим незаполненный узел или не дойдем до корня. В последнем случае корень разбивается на два узла и высота дерева увеличивается.
 +
Добавление ключа в B-дереве может быть осуществлена за один нисходящий проход от корня к листу. Для этого не нужно выяснять, требуется ли разбить узел, в который должен вставляться новый ключ. При проходе от корня к листьям в поисках места для нового ключа будут разбиваться все заполненные узлы, которые будут пройдены (включая и сам лист). Таким образом, если надо разбить какой-то полный узел, гарантируется, что его родительский узел не будет заполнен.
 +
 +
 +
Вставка ключа в B-дерево <tex>T</tex> высоты <tex>h</tex> за один нисходящий проход по дереву потребует <tex>O(h)</tex> обращений к диску и <tex>O(th)=O(t \log_t n)</tex> процессорного времени.
 +
 +
'''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)
 +
 +
Функция <tex>\operatorname{B-Tree-Insert-Nonfull}</tex> вставляет ключ <tex>k</tex> в узел <tex>x</tex>, который должен быть незаполненным при вызове.
 +
Использование функции <tex>\operatorname{B-Tree-Split-Child}</tex> гарантирует, что рекурсия не встретится с заполненным узлом.
 +
Ниже показана вставка ключей <tex>B</tex>, <tex>Q</tex>, <tex>L</tex> и <tex>F</tex> в дерево с <tex>t = 3</tex>, т.е. узлы могут содержать не более <tex>5</tex> ключей
 +
[[Файл:B3insa.png|550px]]
 +
 +
 +
=== Разбиение узла ===
 +
Функция <tex>\operatorname{B-Tree-Split-Child}</tex> получает в качестве входного параметра незаполненный внутренний узел <tex>x</tex> (находящийся в оперативной памяти), индекс <tex>t</tex> и узел <tex>y</tex> (также находящийся в оперативной памяти), такой что <tex>y = c_i[x]</tex> является заполненным дочерним узлом <tex>x</tex>. Процедура разбивает дочерний узел на два и соответствующим образом обновляет поля <tex>x</tex>, внося в него информацию о новом дочернем узле. Для разбиения заполненного корневого узла мы сначала делаем корень дочерним узлом нового пустого корневого узла, после чего можно вызвать функцию. При этом высота дерева увеличивается на <tex>1</tex>. Отметим, что увеличить высоту B-дерева можно только разбиением.
 +
 +
[[Файл:B3splt.PNG|550px|Разбиение узла B-дерева с t=4]]
 +
 +
'''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)
 +
 +
=== Удаление ключа ===
 +
Операция удаления ключа несколько сложнее, нежели добавление оного, так как необходимо убедиться, что удаляемый ключ находится во внутреннем узле. Процесс похож на поиск подходящего места для вставки ключа, с той разницей, что перед спуском в поддерево проверяется, достаточность количества ключей (т.е. <tex>\geqslant t</tex>) в нем, а также возможность провести удаление, не нарушив структуры B-дерева. Таким образом, удаление аналогично вставке, и его проведение не потребует последующего восстановления структуры B-дерева. Если поддерево, выбранное поиском для спуска, содержит минимальное количество ключей <tex>t-1</tex>, производится либо перемещение, либо слияние. Удаление из листа и из внутреннего узла рассмотрено, а также операции слияния поддеревьев и перемещения ключей при удалении ключа рассмотрены ниже.
 +
Для удаления требуется время <tex>O(t \log_t n)</tex> и <tex>O(h)</tex> дисковых операций.
 +
 +
==== Удаление ключа из листа ====
 +
Если удаление происходит из листа, смотрим на количество ключей в нем. Если ключей больше <tex>t - 1</tex>, то просто удаляем ключ.
 +
 +
[[Файл:B3dell.PNG|550px|Удаление <tex>F</tex> из листа]]
 +
В противном случае, если существует соседний лист с тем же родителем, который содержит больше <tex>t - 1</tex> ключа, выберем ключ-разделитель из соседа разделяющий оставшиеся ключи соседа и ключи исходного узла (то есть не больше всех из одной группы и не меньше всех из другой). Обозначим этот ключ как <tex>k_1</tex>. Выберем другой ключ из родительского узла, разделяющий исходный узел и его соседа, который был выбран ранее. Этот ключ обозначим <tex>k_2</tex>. Удалим из исходного узла ключ, который нужно было удалить, спустим в этот узел <tex>k_2</tex>, а вместо <tex>k_2</tex> в родительском узле поставим <tex>k_1</tex>. Если все соседи содержат по <tex>t - 1</tex> ключу, то [[B-дерево#.D0.A1.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5|объединяем]] узел с каким-либо из соседей, удаляем ключ, и ключ из родительского узла, который был разделителем разделённых соседей, [[B-дерево#.D0.9F.D0.B5.D1.80.D0.B5.D0.BC.D0.B5.D1.89.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BA.D0.BB.D1.8E.D1.87.D0.B0|переместим]] в новый узел.
 +
 +
==== Удаление ключа из внутреннего узла ====
 +
Рассмотрим удаление из внутреннего узла. Имеется внутренний узел <tex>x</tex> и ключ, который нужно удалить, <tex>k</tex>. Если дочерний узел, предшествующий ключу <tex>k</tex>, содержит больше <tex>t - 1</tex> ключа, то находим <tex>k_1</tex> – предшественника <tex>k</tex> в поддереве этого узла. Удаляем его. Заменяем <tex>k</tex> в исходном узле на <tex>k_1</tex>. Проделываем аналогичную работу, если дочерний узел, следующий за ключом <tex>k</tex>, имеет больше <tex>t - 1</tex> ключа. Если оба (следующий и предшествующий дочерние узлы) имеют по <tex>t - 1</tex> ключу, то [[B-дерево#.D0.A1.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5|объединяем]] этих детей, [[B-дерево#.D0.9F.D0.B5.D1.80.D0.B5.D0.BC.D0.B5.D1.89.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BA.D0.BB.D1.8E.D1.87.D0.B0|переносим]] в них <tex>k</tex>, а далее удаляем <tex>k</tex> из нового узла. Если [[B-дерево#.D0.A1.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5|сливаются]] <tex>2</tex> последних потомка корня – то они становятся корнем, а предыдущий корень освобождается.
 +
 +
[[Файл:B3delin.png|550px|Удаление M и G из внутренних узлов]]
 +
 +
==== Перемещение ключа ====
 +
Если выбранное для нисходящего прохода поддерево содержит минимальное количеcтво ключей <tex>t-1</tex>, и предшествующие и следующие узлы-братья имеют по меньшей мере <tex>t</tex> ключей, то ключ перемещается в выбранный узел. Поиск выбрал для спуска <tex>x.c_2</tex> (<tex>x.k_1<k_{delete}<x.k_2</tex>). Этот узел имеет лишь <tex>t-1</tex> ключ (красная стрелка). Так как следующий брат <tex>x.c_3</tex> содержит достаточное количество ключей, самый маленький ключ <tex>x.c_3.k_1</tex> может перемещаться оттуда в родительский узел, чтобы переместить, в свою очередь, ключ <tex>x.k_2</tex> как дополнительный ключ в выбранный для спуска узел. Левое поддерево <tex>x.c_3.k_1</tex> — новое правое поддерево перемещённого ключа <tex>x.k_2</tex>.
 +
 +
[[Файл:BTMv.png|450px|Перемещение ключа в B-дереве]]
 +
Легко убедиться в том, что эти повороты поддерживают структуру B-дерева: для всех ключей <tex>k</tex> на отложенном поддереве до и после перенесения выполняется условие <tex>x.k_2 \leqslant k \leqslant x.c_3.k_1</tex>. Симметричная операция может производиться для перенесения ключа из предшествующего брата.
 +
 +
==== Слияние ====
 +
Ниже будет рассмотрено слияние узлов при удалении ключей, то есть слияние узлов равной степени и высоты. Для произвольных же слияний потребуется приведение сливаемых деревьев к одной степени и высоте.
 +
 +
Итак, если выбранное для спуска поддерево <tex>x.c_2</tex> и предшествующий и следующий узел-брат содержит минимальное количество ключей, то перемещение не возможно. На иллюстрации приводится слияние выбранного поддерева с предшествующим или следующим братом для такого случая. Для этого откладывается ключ из родительского узла <tex>x</tex>, который разделяет ключи на два сливаемых узла, в то время средний ключ перемещается в слитый узел. Ссылки на слитые дочерние узлы заменяются ссылкой на новый узел.
 +
 +
[[Файл:BTMg.png|450px|Слияние узла с братом]]
 +
Так как алгоритм гарантирует, что узел, в который будет совершаться спуск, содержит по меньшей мере <tex>t</tex> ключей вместо требуемых условиями B-дерева <tex>t - 1</tex> ключей, родительский узел <tex>x</tex> содержит достаточное количество ключей, чтобы выделить ключ для слияния. Это условие может быть нарушено, только в  том случае, если два ребенка корня сливаются, так как поиск начинается с этого узла. По условиям B-дерева у корня должен быть как минимум один ключ, если дерево не пусто. При слиянии двух последних детей корня последний ключ перемещается во вновь возникшего единственного ребёнка, что приводит к пустому корневому узлу в не пустом дереве. В этом случае пустой узел корня удаляется и заменяется на единственного ребенка.
 +
 +
== Вариации B-дерева ==
 +
=== B+-дерево ===
 +
В B-дереве вместе с ключом может храниться только указатель на другую дисковую страницу, содержащую сопутствующую информацию для данного ключа. Существует распространённая модификация B-дерева, называемая [[B+-дерево|B+-деревом]], в которой, вся сопутствующая информация хранится в листьях, а во внутренних узлах хранятся только ключи и указатели на дочерние узлы. Таким образом удается получить максимально возможную степень ветвления во внутренних узлах.
 +
 +
=== B*-дерево ===
 +
Распространённая модификация B-дерева, в которой каждый внутренний узел должен быть заполнен как минимум на две трети, а не наполовину, как в случае со стандартным B-деревом. Используется в файловых системах HFS и Reiser4. В отличие от B+-деревьев, узел не разбивается на <tex>2</tex> узла, если полностью заполнен. Вместо этого ищется место в уже существующем соседнем узле, и только после того, как оба узла будут заполнены, они разделяются на три узла.
  
== Добавление ключа ==
+
=== 2-3 дерево ===
 +
Производное от B+-дерева. Каждый узел может иметь либо <tex>2</tex>, либо <tex>3</tex> ребёнка.
  
Ищем лист, в который можно добавить ключ, совершая проход от корня к листьям. Если найденный узел не заполнен, добавляем в него ключ. Иначе разбиваем узел на два узла, в первый добавляем первые <tex>t - 1</tex> ключей, во второй — последние <tex>t - 1</tex> ключей. Добавляем ключ в один из этих узлов. Оставшийся средний элемент добавляем в узел родителя, если он заполнен — повторяем пока не встретим не заполненный узел или не дойдем до корня. В последнем случае корень разбивается на два узла и высота дерева увеличивается.
+
== См. также ==
 +
* [[2-3 дерево]]
 +
* [[B+-дерево]]
 +
* [[Splay-дерево]]
 +
* [[АВЛ-дерево]]
 +
* [[Красно-черное дерево]]
  
== Удаление ключа ==
+
== Источники информации ==
 +
* T. H. Cormen «Introduction to Algorithms» third edition, Chapter 18
 +
* Т. Кормен «Алгоритмы: построение и анализ» второе издание, глава 18
 +
* Д. Кнут «Искусство программирования. Сортировка и поиск», часть 6.2.4
 +
* [http://habrahabr.ru/post/114154/ habrahabr.ru {{---}} B-tree]
 +
* [http://de.wikipedia.org/wiki/B-Baum Wikipedia {{---}} B-Baum]
 +
* [http://citforum.ru/programming/theory/sorting/sorting2.shtml#5 Методы сортировки и поиска. Методы поиска во внешней памяти]
 +
* [http://www.ibm.com/developerworks/ru/library/l-data_structures_10/ IBM. developerWorks. «Работа со структурами данных в языках Си и Python: Часть 10. B-деревья и TRIE-деревья»]
 +
* [http://www.minet.uni-jena.de/dbis/lehre/ws2005/dbs1/Bayer_hist.pdf R. Bayer, E. McCreight  «Organization and Maintenance of Large Ordered Indexes», Acta Informatica, 1972]
  
Находим ключ, который необходимо удалить
+
[[Категория:Дискретная математика и алгоритмы]]
# Если удаление происходит из листа, смотрим на количество ключей в нем. Если ключей больше t - 1, то просто удаляем ключ. В противном случае, если существует соседний лист, который содержит больше t - 1 ключа, удалим ключ из исходного узла, на его место поставим ключ-разделитель между исходным узлом и его соседом, а на его место поставим первый, если сосед правый, или последний, если сосед левый, ключ соседа. Если все соседи содержат по t - 1 ключу, то объединяем узел с каким-либо из соседей, удаляем ключ и добавляем ключ-разделитель между узлами в объединенный узел. Если в родительском узле осталось меньше t - 1 ключа, аналогичным образом добавляем в него ключи из соседей или объединяем узел в ними.
+
[[Категория: Структуры данных]]
# Если удаление происходит не из листа, удаляем самый левый ключ из поддерева следующего дочернего узла или самый правый из поддерева предыдущего дочернего узла и ставим удаленный ключ на место удаляемого ключа в исходном узле.
+
[[Категория:Деревья поиска]]

Текущая версия на 19:33, 4 сентября 2022

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] ключей. После добавляем ключ в один из этих узлов. Оставшийся средний элемент добавляется в родительский узел, где становится разделительной точкой для двух новых поддеревьев. Разбиение корня с t = 4. Корневой узел r разделяется на два узла, и создаётся новый корень s. Новый корень содержит средний ключ r и две половины r в качестве детей. Разбиением узла высота дерева увеличивается на единицу

Если и родительский узел заполнен — повторяем пока не встретим незаполненный узел или не дойдем до корня. В последнем случае корень разбивается на два узла и высота дерева увеличивается. Добавление ключа в 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] ключей B3insa.png


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

Функция [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-дерева можно только разбиением.

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

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]F[/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] последних потомка корня – то они становятся корнем, а предыдущий корень освобождается.

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

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

Если выбранное для нисходящего прохода поддерево содержит минимальное количе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-дереве Легко убедиться в том, что эти повороты поддерживают структуру 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] ребёнка.

См. также

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