Исследование производительности процессора обработки структур в системе…
5
ции информации в вершинах
Каталога
они объединены в независи-
мые списки, которые автоматически модифицируются по мере уве-
личения или сокращения размеров структур. Максимальное количе-
ство структур, хранимых в СП, соответствует количеству блоков на
верхнем уровне дерева (в текущей версии — восемь). Структура с
номером «0» выполняет специальную функцию: хранение информа-
ции о свободных вершинах дерева. В начальный момент времени эта
структура занимает всю локальную память данных и становится пу-
стой в случае полного заполнения памяти информацией. Инициали-
зация структуры 0, включающая указание всех атрибутов и адресов
локальной памяти данных, выполняется автоматически за один такт
работы СП.
Рис. 1.
Аппаратная реализация
B
+ дерева
На нижнем уровне
B
+ дерева ключи и информация хранятся в
виде блоков данных, которые содержат в упорядоченном виде от од-
ной до шести пар «ключ-значение». Для осуществления основных
операций со структурами все блоки, соответствующие вершинам
Каталога
n
–1 уровня, загружаются из памяти данных в
Операцион-
ный буфер
СП [4]. Все загруженные в данный момент вершины ката-
лога для всех уровней дерева, а также заполненный
Операционный
буфер
представляют собой трассу дерева (выделена на рис. 1 серым
цветом), обращение к которой возможно за наименьшее время, так
как при этом не требуется доступ в локальную память данных СП.
При выполнении операции
Поиска
происходит восходящий поиск
информации в трассе до тех пор, пока не будет найден искомый путь,
либо не будет достигнут уровень 0. После этого выполняется нисхо-
дящее движение в дереве до уровня
n
–1. Использование загруженной
