Удаление элементов из Б-дерева

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

Чтобы удалить элемент из листа, сначала необходимо сдвинуть все другие элементы влево, чтобы заполнить оставшееся место. Однако следует помнить, что каждый узел в Б-дереве порядка К должен содержать от К до 2К элементов. После удаления элемента из листа, он может содержать всего К-1 элементов. В этом случае необходимо взять несколько элементов з узлов на том же уровне, а затем перераспределить элементы так, чтобы узлы содержали не менее К элементов. На рис. 22 элемент был удален из крайнего левого листа в дереве, при этом узел остался всего с одним элементом. Перераспределение элементов между узлом и его правым сестринским дает обоим узлам, по крайней мере, по два ключа. Следует обратить внимание, что средний элемент J сдвинут в родительский узел.

Рис. 22. Перераспределение узлов после удаления одного из них

При попытке сбалансировать дерево таким образом может оказаться, что соседний узел на том же уровне содержит всего К элементов, поэтому недостаточно использовать эти два узла. В этом случае все элементы в обоих узлах могут поместиться в пределах одного узла, поэтому их можно объединить их.

Процесс объединения двух узлов называется слиянием сегментов. На рис. 23 показан пример такого слияния.

Рис. 23. Процесс объединения сегментов

При слиянии двух узлов из родительского удаляется ключ, и там остается К-1 элементов. В этом случае необходимо перебалансировать или объединить его с одним из сестринских узлов. Но если после этого в узле на более высоком уровне все равно останется К-1 элементов, процесс повторится. В наихудшем случае удаление вызовет цепную реакцию слияния сегментов узлов вплоть до корня.

Нисходящие Б-деревья

Данный вид Б-деревьев основан на немного отличном алгоритме добавления узлов. Так, в случае добавления узла в дерево происходит автоматическое разбиение всех полных узлов, которые встречаются на пути сверху вниз при поиске необходимого места для вставки. Так как все расположенные выше полные узлы уже разбиты, то в родительском узле всегда есть место для нового элемента.

Когда процедура достигает листа, в который нужно поместить элемент, в родительском узле обязательно будет место для размещения нового элемента. Если программа должна разбить лист, то всегда есть место для размещения среднего элемента листа в родительском узле. Поскольку эта система работает от вершины вниз, этот тип Б-деревьев называется нисходящим Б-деревом (top-down B-trees).

При этом разбиение блоков происходит чаще, чем необходимо. Нисходящее Б-дерево разбивает полный узел, даже если в его дочерних узлах достаточно много свободного места. При нисходящем методе дерево содержит большее количество пустых записей, чем в случае обычных Б-деревьев, однако тем самым сокращается риск возникновения длинного каскада разбиений сегментов.

К сожалению, не существует нисходящей версии объединения узлов. Процедура удаления узлов не может объединять встречающиеся полупустые узлы на пути вниз, потому что в этот момент еще неизвестно, нужно ли будет объединить два дочерних узла и удалить элемент из их родителя. Поскольку также неизвестно, будет ли удален элемент из родительского узла, нельзя заранее сказать, потребуется ли слияние родителя с одним из узлов, находящимся на том же уровне.

Б+деревья

Б-деревья часто используются для хранения больших записей. Типичное Б-дерево может содержать записи о сотрудниках, каждая из которых занимает несколько килобайт памяти. Записи упорядочиваются по некоторому ключевому полю, например по имени служащего или идентификационному номеру. В этом случае переупорядочивание элементов будет происходить медленно. Чтобы объединить два сегмента, программа должна переместить много записей, каждая из которых довольно большая. Аналогично, для разбиения блока придется обработать не меньшее число, записей большого объема.

Чтобы избежать перемещения больших блоков данных, программа записывает во внутренних узлах Б-дерева только ключи записей. Узлы также содержат указатели на фактические записи данных, сохраненные в другом месте. Теперь, если программе требуется переупорядочить блоки, нужно будет переместить только ключи и указатели, а не сами записи. Данный тип Б-дерева называется Б+деревом (B+tree).

Поскольку элементы Б+ дерева довольно малы, программа сохраняет большее количество ключей в каждом узле. При том же размере узла программа может увеличить порядок дерева и сделать его короче.

Сортировка

Под сортировкой записей будем понимать сортировку в порядке не убывания их ключей .

2.1 Внутренняя сортировка [16]

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

Сортировка путем вставок

Предполагается, что перед рассмотрением записи R_j предыдущие записи R₁,...,R_j-1 уже упорядочены. Задача состоит в необходимости вставить данную запись таким образом, чтобы массив оставался упорядоченным.

Метод простых вставок. Пусть 1 < j < N и записи R₁,...,R_j-1 уже размещены так, что K₁<=K₂<=…<=K_j-1. Необходимо производить сравнения ключа K_j с ключами K_j-1, K_j-2 ... до тех пор, пока не обнаружится, что запись R_j следует вставить между R_i и R_i+1. В этом случае необходимо сдвинуть записи R_i+1,..., R_j-1 на одну позицию вверх и поместить новую запись в позицию i + 1. операции сравнения и перемещения удобно совмещать, перемежая их между собой. Поскольку запись R_j как бы "погружается" на положенный ей уровень, этот способ часто называют просеиваниемилипогружением.