Изменения

== '''B-дерево ==<wikitex>''' (англ. ''B-деревоtree''' — ) {{---}} сильноветвящееся сбалансированное дерево поиска, позволяющее проводить поиск, добавление и удаление элементов за $<tex>O(\log n)$</tex>. B-деревья схожи с [[Красно-черное дерево|красно-черными деревьями]] в том, что B-дерево с $<tex>n$ </tex> узлами имеют имеет высоту $<tex>O(\lg log n)$, но отличаются от [[Красно-черное дерево|них]] количеством </tex>. Количество детей узлов — может быть от нескольких до тысяч (обычно степень ветвления B-дерева определяется характеристиками устройства (дисков), на котором производится работа с деревом). Сама высота B-дерева может быть значительно меньше чем у [[Красно-черное дерево|красно-черного дерева]], из-за его ветвистости, и, следовательно, основание логарифма, выражающего высоту дерева, может быть намного больше. Таким образом, В-деревья также могут использоваться для реализации многих операций над динамическими множествами за время $<tex>O(\lg log n)$ B-дерево было впервые предложено Р. Бэйером и Е. МакКрейтом в 1970 году.</wikitextex>

Каждый узел B-дерева, кроме корня, содержит от === Структура узла === '''struct''' Node '''bool''' leaf <texspan style="color:#008000">t - 1 // является ли узел листом</texspan> до '''int''' n <texspan style="color:#008000">2t - 1 // количество ключей узла</texspan> ключей. Корень содержит от '''int''' key[] <texspan style="color:#008000">1 // ключи узла</texspan> до '''Node''' c[] <texspan style="color:#008000">2t - 1 // указатели на детей узла</texspan> ключей. === Структура дерева === '''struct''' BTree '''int''' t <texspan style="color:#008000">t // минимальная степень дерева</texspan> — параметр дерева, не меньший '''Node''' root <texspan style="color:#008000">2 // указатель на корень дерева</texspan>. Ключи в каждом узле упорядочены.

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

В типичном приложении Для того чтобы снизить время ожидания, связанное с B-деревоммеханическим перемещением, при обращении к диску выполняется обращение одновременно сразу к нескольким элементам, объём хранимой информации так великхранящимся на диске. Информация разделяется на несколько страниц одинакового размера, что вся она просто не может храниться которые хранятся последовательно друг за другом в основной памяти единовременно. Алгоритмы B-дерева копируют выбранные страницы пределах одного цилиндра (мера информации набора дорожек на дисках; обычнона одном расстоянии от центра), и каждая операция чтения или записи работает сразу с несколькими страницами. Для типичного диска размер страницы варьируется от $<tex>2^{11}$ </tex> до $2^{14}$ Байт) с диска в основную память по мере надобности и записывает обратно <tex>16</tex> КБайт. После того, как головка установлена на нужную дорожку, а диск поворачивается так, что головка становится на начало интересующей нас страницы, которые были изменены. Алгоритмы B-дерева хранят лишь определённое количество страниц в основной памяти в любой момент времени; таким образомчтение и запись становятся полностью электронными процессами, объём основной памяти не ограничивает размер B-деревьевзависящими от поворота диска, которыми можно управлятьи диск может быстро читать или писать крупные объёмы данных.</wikitex>

Ищем лист, в который можно добавить ключ, совершая проход от корня к листьям. Если найденный узел не заполненнезаполнен, добавляем в него ключ. Иначе разбиваем узел на два узла, в первый добавляем первые <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 - 1</tex>) в нем, то просто удаляем ключа также возможность провести удаление, не нарушив структуры B-дерева. Таким образом, удаление аналогично вставке, и его проведение не потребует последующего восстановления структуры B-дерева. В противном случаеЕсли поддерево, если существует соседний листвыбранное поиском для спуска, который содержит больше минимальное количество ключей <tex>t - 1</tex> ключа, удалим ключ производится либо перемещение, либо слияние. Удаление из листа и из исходного внутреннего узларассмотрено, на его место поставим ключ-разделитель между исходным узлом а также операции слияния поддеревьев и его соседом, а на его место поставим первый, если сосед правый, или последний, если сосед левый, ключ соседаперемещения ключей при удалении ключа рассмотрены ниже. Если все соседи содержат по Для удаления требуется время <tex>O(t - 1\log_t n)</tex> ключу, то объединяем узел с каким-либо из соседей, удаляем ключ и добавляем ключ-разделитель между узлами в объединенный узел. Если в родительском узле осталось меньше <tex>t - 1O(h)</tex> ключа, аналогичным образом добавляем в него ключи из соседей или объединяем узел в ними.# Если удаление происходит не из листа, удаляем самый левый ключ из поддерева следующего дочернего узла или самый правый из поддерева предыдущего дочернего узла и ставим удаленный ключ на место удаляемого ключа в исходном узледисковых операций.

== Ссылки == Удаление ключа из листа ====* TЕсли удаление происходит из листа, смотрим на количество ключей в нем. Если ключей больше <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. HD0. Cormen «Introduction to Algorithms» third editionB5|объединяем]] узел с каким-либо из соседей, удаляем ключ, Chapter 18и ключ из родительского узла, который был разделителем разделённых соседей, [[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>, часть 6а далее удаляем <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>.4* [[httpФайл:BTMv.png|450px|Перемещение ключа в B-дереве]]Легко убедиться в том, что эти повороты поддерживают структуру B-дерева: для всех ключей <tex>k</tex> на отложенном поддереве до и после перенесения выполняется условие <tex>x.k_2 \leqslant k \leqslant x.c_3.k_1</habrahabrtex>. Симметричная операция может производиться для перенесения ключа из предшествующего брата. ==== Слияние ====Ниже будет рассмотрено слияние узлов при удалении ключей, то есть слияние узлов равной степени и высоты. Для произвольных же слияний потребуется приведение сливаемых деревьев к одной степени и высоте.  Итак, если выбранное для спуска поддерево <tex>x.c_2</tex> и предшествующий и следующий узел-брат содержит минимальное количество ключей, то перемещение не возможно. На иллюстрации приводится слияние выбранного поддерева с предшествующим или следующим братом для такого случая. Для этого откладывается ключ из родительского узла <tex>x</tex>, который разделяет ключи на два сливаемых узла, в то время средний ключ перемещается в слитый узел. Ссылки на слитые дочерние узлы заменяются ссылкой на новый узел.  [[Файл:BTMg.rupng|450px|Слияние узла с братом]]Так как алгоритм гарантирует, что узел, в который будет совершаться спуск, содержит по меньшей мере <tex>t</posttex> ключей вместо требуемых условиями B-дерева <tex>t - 1</114154tex> ключей, родительский узел <tex>x</ tex> содержит достаточное количество ключей, чтобы выделить ключ для слияния. Это условие может быть нарушено, только в Хабрахабртом случае, если два ребенка корня сливаются, так как поиск начинается с этого узла. По условиям B-treeдерева у корня должен быть как минимум один ключ, если дерево не пусто. При слиянии двух последних детей корня последний ключ перемещается во вновь возникшего единственного ребёнка, что приводит к пустому корневому узлу в не пустом дереве. В этом случае пустой узел корня удаляется и заменяется на единственного ребенка. == Вариации B-дерева ===== B+-дерево ===В B-дереве вместе с ключом может храниться только указатель на другую дисковую страницу, содержащую сопутствующую информацию для данного ключа. Существует распространённая модификация B-дерева, называемая [[B+-дерево|B+-деревом]], в которой, вся сопутствующая информация хранится в листьях, а во внутренних узлах хранятся только ключи и указатели на дочерние узлы. Таким образом удается получить максимально возможную степень ветвления во внутренних узлах. === B*-дерево ===Распространённая модификация B-дерева, в которой каждый внутренний узел должен быть заполнен как минимум на две трети, а не наполовину, как в случае со стандартным B-деревом. Используется в файловых системах HFS и Reiser4. В отличие от B+-деревьев, узел не разбивается на <tex>2</tex> узла, если полностью заполнен. Вместо этого ищется место в уже существующем соседнем узле, и только после того, как оба узла будут заполнены, они разделяются на три узла. === 2-3 дерево ===Производное от B+-дерева. Каждый узел может иметь либо <tex>2</tex>, либо <tex>3</tex> ребёнка.