Улучшение производительности б‑деревьев

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

=======177

Балансировка для устранения разбиения блоков

При добавлении элемента к блоку, который уже заполнен, блок разбивается на два. Этого можно избежать, если выполнить балансировку этого узла с одним из узлов на том же уровне. Например, вставка нового элемента Q в Б‑дерево, показанное слева на рис. 7.20 обычно вызывает разбиение блока. Этого можно избежать, выполнив балансировку узла, содержащего J, K, L и N и левого узла на том же уровне, содержащего B и E. При этом получается дерево, показанное на рис. 7.20 справа.

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

Что более важно, если не нужно будет разбиение блоков, то не понадобится и перемещение элемента в родительский узел. Это предотвращает возникновение длительной последовательности разбиений блоков.

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

Добавление свободного пространства

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

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

В реальных приложениях Б‑деревья обычно имеют намного больший порядок, чем деревья, приведенные здесь. Добавление свободного пространства в дерево значительно уменьшает необходимость балансировки и разбиения блоков. Например, можно добавить в Б‑дерево 10 порядка 10 процентов свободного пространства, чтобы в каждом узле было место еще для двух элементов. С таким деревом можно будет работать достаточно долго, прежде чем возникнут длинные цепочки разбиений блоков.

Это очередной пример пространственно‑временного компромисса. Добавка в узлы пустого пространства увеличивает размер дерева, но уменьшает вероятность разбиения блоков.

@Рис. 7.20. Балансировка для устранения разбиения блоков

=======178

@Рис. 7.21. Плотное заполнение Б‑дерева