286
правок
Изменения
Нет описания правки
'''B-дерево''' (англ. ''B-tree'') {{---}} сильноветвящееся сбалансированное дерево поиска, позволяющее проводить поиск, добавление и удаление элементов за <tex>O(\log n)</tex>. B-дерево с <tex>n<n/tex> узлами имеет высоту <tex>O(\log n)</tex>. Количество детей узлов может быть от нескольких до тысяч (обычно степень ветвления B-дерева определяется характеристиками устройства (дисков), на котором производится работа с деревом). В-деревья также могут использоваться для реализации многих операций над динамическими множествами за время <tex>O(\log n)</tex>
B-дерево было впервые предложено Р. Бэйером и Е. МакКрейтом в <tex>1970</tex> году.
=== Добавление ключа ===
Ищем лист, в который можно добавить ключ, совершая проход от корня к листьям. Если найденный узел незаполнен, добавляем в него ключ. Иначе разбиваем узел на два узла, в первый добавляем первые <tex>t - 1</tex> ключей, во второй — последние <tex>t - 1</tex> ключей. После добавляем ключ в один из этих узлов. Оставшийся средний элемент добавляется в родительский узел, где становится разделительной точкой для двух новых поддеревьев.
[[Файл:B3inssp.png|550px|Разбиение корня с <tex>t = 4</tex>. Корневой узел <tex>r</tex> разделяется на два узла, и создаётся новый корень <tex>s</tex>. Новый корень содержит средний ключ <tex>r</tex> и две половины <tex>r</tex> в качестве детей. Разбиением узла высота дерева увеличивается на единицу]]
Если и родительский узел заполнен — повторяем пока не встретим незаполненный узел или не дойдем до корня. В последнем случае корень разбивается на два узла и высота дерева увеличивается.
Рассмотрим удаление из внутреннего узла. Имеется внутренний узел <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|Удаление <tex>M</tex> и <tex>G</tex> из внутренних узлов]]
==== Перемещение ключа ====
