Сбалансированное двоичное дерево с миллионом элементов имело бы высоту log2(1.000.000), или около 20. Тем не менее, узлы двоичного дерева содержат всего по одному ключевому значению. Для поиска элемента в двоичном дереве, пришлось бы проверить 20 узлов и 20 значений. Для поиска элемента в Б‑дереве пришлось бы проверить 5 узлов и 100 ключей.
Применение Б‑деревьев может обеспечить более высокую скорость работы, если проверка ключей выполняется относительно просто, в отличие от проверки узлов. Например, если база данных находится на диске, чтение данных с диска может происходить достаточно медленно. Когда же данные находятся в памяти, их проверка может происходить очень быстро.
Чтение данных с диска происходит большими блоками, и считывание целого блока занимает столько же времени, сколько и чтение одного байта. Если узлы Б‑дерева не слишком велики, то чтение узла Б‑дерева с диска займет не больше времени, чем чтение узла двоичного дерева. В этом случае, для поиска 5 узлов в Б‑дереве потребуется выполнить 5 медленных обращений к диску, плюс 100 быстрых обращений к памяти. Поиск 20 узлов в двоичном дереве потребует 20 медленных обращений к диску и 20 быстрых обращений к памяти, при этом поиск в двоичном дереве будет более медленным, поскольку время, затраченное на 15 лишних обращений к диску будет намного больше, чем сэкономленное время 80 обращений к памяти. Вопросы, связанные с обращением к диску, позднее обсуждаются в этой главе более подробно.
Чтобы вставить новый элемент в Б‑дерево, найдем лист, в который он должен быть помещен. Если этот узел содержит менее, чем 2 * K ключей, то в этом узле остается место для добавления нового элемента. Вставим новый узел на место так, чтобы порядок элементов внутри узла не нарушился.
Если узел уже содержит 2 * K элементов, то места для нового элемента в узле уже не остается. Разобьем тогда узел на два новых узла, поместив в каждый из них K элементов в правильном порядке. Затем средний элемент переместим в родительский узел.
Например, предположим, что мы хотим поместить новый элемент Q в Б‑дерево, показанное на рис. 7.15. Этот новый элемент должен находиться во втором листе, который уже заполнен. Для разбиения этого узла, разделим элементы J, K, L, N и Q между двумя новыми узлами. Поместим элементы J и K в левый узел, а элементы N и Q — в правый. Затем переместим средний элемент, L[RV13] в родительский узел. На рис. 7.16 показано новое дерево.
@Рис. 7.16. Б‑дерево после вставки элемента Q
=========173
Разбиение узла на два называется разбиением блока. Когда оно происходит, к родительскому узлу добавляется новый ключ и новый указатель. Если родительский узел уже заполнен, то это также может привести к его разбиению. Это, в свою очередь, потребует добавления новой записи на более высоком уровне и так далее. В наихудшем случае, вставка элемента вызовет «цепную реакцию», которая приведет к изменениям на всех вышележащих уровнях вплоть до разбиения корневого узла.
Когда происходит разбиение корневого узла, Б‑дерево становится выше. Это единственный случай, при котором его высота увеличивается. Поэтому Б‑деревья обладают необычным свойством — они всегда растут от листьев к корню.
Теоретически, удалить узел из Б‑дерева так же просто, как и вставить его. На практике, детали этого процесса достаточно сложны.
Если удаляемый узел не является листом, то его нужно заменить другим элементом, чтобы сохранить порядок элементов. Это похоже на случай удалений элемента из упорядоченного дерева или АВЛ‑дерева и его можно обрабатывать аналогично. Заменим элемент самым крайним правым элементом из левой ветви. Этот элемент всегда будет листом. После замены элемента, можно просто считать, что вместо него просто удален заменивший его лист.
Чтобы удалить элемент из листа, вначале нужно при необходимости сдвинуть все другие элементы влево, чтобы заполнить образовавшееся пространство. Помните, что каждый узел в Б‑дереве порядка K должен иметь от K до 2 * K элементов. После удаления элемента из листа, может оказаться, что он содержит всего K - 1 элементов.
В этом случае, можно попробовать взять несколько элементов из узлов на том же уровне. Затем можно распределить элементы в двух узлах так, чтобы они оба имели не меньше K элементов. На рис. 7.17 элемент удаляется из самого левого листа дерева, при этом в нем остается всего один элемент. После перераспределения элементов между узлом и правым узлом на том же уровне, оба узла имеют не меньше двух ключей. Заметьте, что средний элемент J перемещается в родительский узел.
@Рис. 7.17. Балансировка после удаления элемента
=======174
@Рис. 7.18. Слияние после удаления элемента
При попытке сбалансировать дерево таким образом, может оказаться, что соседний узел на том же уровне содержит всего K элементов. Тогда два узла вместе содержат всего 2 * K - 1 элементов, что недостаточно для заполнения двух узлов. В этом случае, все элементы из обоих узлов могут поместиться в одном узле, поэтому их можно слить. Удалим ключ, который отделяет два узла от родителя. Поместим этот элемент и 2 * K - 1 элементов из двух узлов в один общий узел. Этот процесс называется слиянием узлов (bucket merge или bucket join). На рис. 7.18 показано слияние двух узлов.
При слиянии двух узлов, из родительского узла удаляется ключ, при этом в родительском узле может остаться K - 1 элементов. В этом случае, может потребоваться балансировка или слияние родителя с одним из узлов на его уровне. Это также может привести к тому, что в узле на более высоком уровне также останется K - 1 элементов, и процесс повторится. В наихудшем случае, удаление приведет к «цепной реакции» слияний блоков, которая может дойти до корневого узла.
При удалении последнего элемента из корневого узла, два его оставшихся дочерних узла сливаются, образуя новый корень, и дерево при этом становится короче на один уровень. Единственный способ уменьшения высоты Б‑дерева — слияние двух дочерних узлов корня и образование нового корня.
Программа Btree позволяет вам оперировать Б‑деревом. Введите текст, и нажмите на кнопку Add, чтобы добавить элемент в дерево. Для удаления элемента введите его значение и нажмите на кнопку Remove. На рис. 7.19 показано окно программы Btree с Б‑деревом 2 порядка.
@Рис. 7.19. Программа Btree
========175
Существует несколько разновидностей Б‑деревьев, из которых здесь описаны только некоторые. Нисходящие Б‑деревья (top‑down B‑trees) немного иначе управляют структурой Б‑дерева. За счет разбиения встречающихся полных узлов, эта разновидность алгоритма использует при вставке элементов более наглядную нисходящую рекурсию вместо восходящей. Эта также уменьшает вероятность возникновения длительной последовательности разбиений блоков.
Другой разновидностью Б‑деревьев являются Б+деревья (B+trees). В Б+деревьях внутренние узлы содержат только ключи данных, а сами записи находятся в листьях. Это позволяет Б+деревьям хранить в каждом блоке больше элементов, поэтому такие деревья короче, чем соответствующие Б‑деревья.
Подпрограмма, которая добавляет новый элемент в Б‑дерево, вначале выполняет рекурсивный поиск по дереву, чтобы найти блок, в который его нужно поместить. Когда она пытается вставить новый элемент на его место, ей может понадобиться разбить блок и переместить один из элементов узла в его родительский узел.
При возврате из рекурсивных вызовов процедуры, вызывающая процедура проверяет, требуется ли разбиение родительского узла. Если да, то элемент помещается в родительский узел. При каждом возврате из рекурсивного вызова, вызывающая процедура должна проверять, не требуется ли разбиение следующего предка. Так как эти разбиения блоков происходят при возврате из рекурсивных вызовов процедура, это восходящая рекурсия, поэтому иногда Б‑деревья, которыми манипулируют таким образом, называются восходящими Б‑деревьями (bottom‑up B‑trees).
Другая стратегия состоит в том, чтобы разбивать все полные узлы, которые встречаются процедуре на пути вниз по дереву. При поиске блока, в который нужно поместить новый элемент, процедура разбивает все повстречавшиеся полные узлы. При каждом разбиении узла, она помещает один из его элементов в родительский узел. Так как она уже разбила все выше расположенные полные узлы, то в родительском узле всегда есть место для нового элемента.
Когда процедура доходит до листа, в который нужно поместить элемент, то в его родительском узле всегда есть свободное место, и если программе нужно разбить лист, то всегда можно поместить средний элемент в родительский узел. Так как при этом процедура работает с деревом сверху вниз, Б‑деревья такого типа иногда называются нисходящими Б‑деревьями (top‑down B‑trees).
При этом разбиение блоков происходит чаще, чем это абсолютно необходимо. В нисходящем Б‑дереве полный узел разбивается, даже если в его дочерних узлах достаточно много свободного места. За счет предварительного разбиения узлов, при использовании нисходящего метода в дереве содержится больше пустого пространства, чем в восходящем Б‑дереве. С другой стороны, такой подход уменьшает вероятность возникновения длительной последовательности разбиений блоков.
К сожалению, не существует нисходящей версии для слияния узлов. При продвижении вниз по дереву, процедура удаления узлов не может объединять встречающиеся наполовину пустые узлы, потому что в этот момент еще неизвестно, нужно ли будет объединить два дочерних узла и удалить элемент из их родителя. Так как неизвестно также, будет ли удален элемент из родительского узла, то нельзя заранее сказать, потребуется ли слияние родителя с одним из узлов, находящимся на том же уровне.