Реферат: VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования
При слиянии двух узлов, из родительского узла удаляется ключ, при этом в родительском узле может остаться 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).
При этом разбиение блоков происходит чаще, чем это абсолютно необходимо. В нисходящем Б‑дереве полный узел разбивается, даже если в его дочерних узлах достаточно много свободного места. За счет предварительного разбиения узлов, при использовании нисходящего метода в дереве содержится больше пустого пространства, чем в восходящем Б‑дереве. С другой стороны, такой подход уменьшает вероятность возникновения длительной последовательности разбиений блоков.
К сожалению, не существует нисходящей версии для слияния узлов. При продвижении вниз по дереву, процедура удаления узлов не может объединять встречающиеся наполовину пустые узлы, потому что в этот момент еще неизвестно, нужно ли будет объединить два дочерних узла и удалить элемент из их родителя. Так как неизвестно также, будет ли удален элемент из родительского узла, то нельзя заранее сказать, потребуется ли слияние родителя с одним из узлов, находящимся на том же уровне.
==========176
Б+деревья
Б+деревья часто используются для хранения больших записей. Типичное Б‑дерево может содержать записи о сотрудниках, каждая из которых может занимать несколько килобайт памяти. Записи могли бы располагаться в Б‑дереве в соответствии с ключевым полем, например фамилией сотрудника или его идентификационным номером.
В этом случае упорядочение элементов может быть достаточно медленным. Чтобы слить два блока, программе может понадобиться переместить множество записей, каждая из которых может быть достаточно большой. Аналогично, для разбиения блока может потребоваться переместить множество записей большого объема.
Чтобы избежать перемещения больших блоков данных, программа может записывать во внутренних узлах Б‑дерева только ключи. При этом узлы также содержат ссылки на сами записи данных, которые записаны в другом месте. Теперь, если программе требуется переупорядочить блоки, то нужно переместить только ключи и указатели, а не сами записи. Этот тип Б‑дерева называется Б+деревом (B+tree).
То, что элементы в Б+дереве достаточно малы, также позволяет программе хранить больше ключей в каждом узле. При том же размере узла, программа может увеличить порядок дерева и сделать его более коротким.
Например, предположим, что имеется Б‑дерево 2 порядка, то есть каждый узел имеет от трех до пяти дочерних узлов. Такое дерево, содержащее миллион записей, должно было бы иметь высоту между log5(1.000.000) и log3(1.000.000), или между 9 и 13. Чтобы найти элемент в таком дереве, программа должна выполнить от 9 до 13 обращений к диску.
Теперь допустим, что те же миллион записей находятся в Б+дереве, узлы которого имеют примерно тот же размер в байтах. Поскольку в узлах Б+дерева содержатся только ключи, то в каждом узле дерева может храниться до 20 ключей к записям. В этом случае, каждый узел будет иметь от 11 до 21 дочерних узлов, поэтому высота дерева будет от log21(1.000.000) до log11(1.000.000), или между 5 и 6. Чтобы найти элемент, программе понадобится всего 6 обращений к диску для нахождения его ключа, и еще одно обращение к диску, чтобы считать сам элемент.
В Б+деревьях также просто связать с набором записей множество ключей. В системе, оперирующей записями о сотрудниках, одно Б+дерево может использовать в качестве ключей фамилии, а другое — идентификационные номера социального страхования. Оба дерева будут содержать указатели на записи данных, которые будут находиться за пределами деревьев.
Улучшение производительности Б‑деревьев
В этом разделе описаны два метода улучшения производительности Б‑ и Б+деревьев. Первый метод позволяет перераспределить элементы между узлами одного уровня, чтобы избежать разбиения блоков. Второй позволяет помещать пустые ячейки в дерево, чтобы уменьшить вероятность необходимости разбиения блоков в будущем.
=======177
Балансировка для устранения разбиения блоков
При добавлении элемента к блоку, который уже заполнен, блок разбивается на два. Этого можно избежать, если выполнить балансировку этого узла с одним из узлов на том же уровне. Например, вставка нового элемента Q в Б‑дерево, показанное слева на рис. 7.20 обычно вызывает разбиение блока. Этого можно избежать, выполнив балансировку узла, содержащего J, K, L и N и левого узла на том же уровне, содержащего B и E. При этом получается дерево, показанное на рис. 7.20 справа.
Такая балансировка имеет ряд преимуществ. Во‑первых, при этом блоки используются более эффективно. В них находится меньше пустых ячеек, при этом уменьшится количество расходуемой понапрасну памяти.
Что более важно, если не нужно будет разбиение блоков, то не понадобится и перемещение элемента в родительский узел. Это предотвращает возникновение длительной последовательности разбиений блоков.
С другой стороны, уменьшение числа неиспользуемых элементов в дереве увеличивает вероятность необходимости разбиения блоков в будущем. Так как в дереве остается меньше свободных ячеек, то более вероятно, что узел окажется уже полон, когда понадобится вставить новый элемент.
Добавление свободного пространства
Предположим, что имеется небольшая база данных клиентов, содержащая 10 записей. Можно загружать записи в Б‑дерево так, чтобы они заполняли каждый блок целиком, как показано на рис. 7.21. При этом дерево содержит мало свободного пространства, и вставка нового элемента сразу же приводит к разбиению блоков. Фактически, так как все блоки заполнены, она вызовет последовательность разбиения блоков, которая дойдет до корневого узла.
Вместо плотного заполнения дерева, можно добавлять к каждому узлу некоторое количество пустых ячеек, как показано на рис. 7.22. Хотя при этом дерево будет несколько больше, в него можно будет добавлять элементы, не вызывая сразу же последовательность разбиений блоков. После работы с деревом в течение некоторого времени, количество свободного пространства может уменьшиться до такой степени, при которой разбиения блоков могут возникнуть. Тогда можно перестроить дерево, добавив больше свободного пространства.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82
