А.Ю. Попов
8
стые вершины (структура 0 пуста), необходимо выполнить
Деление
на уровне
k
–2 и после этого повторить
Деление
на уровне
k–
1. При
необходимости подъем повторяется до уровня 0. Операция
Деление
в
худшем случае требует
(log )
b
O n
тактов и не требует перезаписи
ключей на нижнем уровне.
В алгоритме управления СП также учтен случай, когда локальная
память данных будет полностью заполнена информацией и операция
Деление
станет невозможной. Когда локальная память данных запол-
нена не на 100 %, происходит частичная или полная дефрагментация
структуры дерева. В результате дерево перестраивается и освобожда-
ется некоторое количество вершин, что делает
Деление
возможным.
Если же пустых поддеревьев и в этом случае не образуется, происхо-
дит цепочечный сдвиг элементов. Такое происходит только при су-
щественном заполнении локальной памяти данных СП. Например,
когда из заполненной памяти удален минимальный элемент структу-
ры и происходит добавление элемента с ключом, бόльшим макси-
мального. Проведенное тестирование СП показало работоспособ-
ность данного алгоритма управления при заполнении памяти СП до
100 %.
Операция
Удаление
в текущем варианте реализации СП, в отли-
чие от программных вариантов, не связана с дефрагментацией струк-
туры. Дефрагментация в программной реализации
B
+ дерева служит
для сохранения компактности представления структуры в оператив-
ной памяти и выполняется с помощью операции
Слияние
, при кото-
рой происходит объединение информации двух вершин в одну, в ре-
зультате чего вторая вершина освобождается. Команда
Удаление
в
СП сводится лишь к выполнению операции
Поиск
, удалению инфор-
мации из
Операционного буфера
и последующей модификации
Ка-
талога
без дефрагментации и
Слияния
. Такое упрощение операции
связано с тем, что, вне зависимости от размера структур, СП хранит
их в виде деревьев постоянной высоты. СП самостоятельно управля-
ет выделением свободных блоков и выполняет дефрагментацию по
необходимости во время операции
Деление
вершин. Предполагается
также, что при паузах между выполнениями основных команд СП
будет проводить частичную дефрагментацию структур самостоя-
тельно, для чего в СП предусмотрена команда
Сжатие
. Таким обра-
зом, дефрагментация производится только тогда, когда это необхо-
димо для размещения новых элементов, или во время вынужденных
простоев СП.
Операция
Поиск
реализована в СП аналогично программным ва-
риантам данного алгоритма в
B
+ дереве [5, 6] и заключается в поиске
вершины
Каталога
, удовлетворяющей условию (Low ≤ key ≤ High).
На нижнем уровне
n
–1 в
Операционном буфере
выполняется поиск
