Исследование производительности процессора обработки структур в системе…
7
Переход к
ДОБАВЛЕНИЕ
ВСЕ ЕСЛИ
ИНАЧЕ
t
=
t
+
d
Переход к
ДОБАВЛЕНИЕ
ВСЕ ЕСЛИ
КОНЕЦ.
Операция
Деление
выполняется в случае переполнения
Каталога
.
Данная операция заключается в выделении для структуры новой
вершины на вышестоящем уровне и переносе в нее части поддеревь-
ев текущего уровня. На рис. 2 представлен пример выполнения опе-
рации
Деление
вершины для
B
+ дерева кратности 4. В примере необ-
ходимо произвести добавление в вершину 1 на уровне
k
–1, далее —
добавление нового элемента, ключ которого находится в интервале
между границей High вершины 5 и Low вершины 6. Однако
Каталог
на уровне
k
оказывается переполнен, и добавление в вершину 5 или 6
невозможно. В этом случае на уровне
k
–1 выполняется добавление
новой вершины номер 3 в структуру 1. Вершина 3 занимает место
между вершинами 1 и 2 и удаляется из структуры 0. На уровне
k
про-
исходит перенос вершины 8 из поддерева вершины 1 в поддерево
вершины 3. Вершина 9 из структуры 0 переносится из поддерева
вершины 3 в поддерево вершины 1 и занимает позицию между вер-
шинами 5 и 6.
Рис. 2.
Операция
Деление
вершины
Каталога
Таким образом, уровень
k Каталога
освобождается и становится
возможным произвести
Добавление
в него новой информации в вер-
шину 9. В случае, когда на вышестоящем уровне
k
–1 отсутствуют пу-
