Основы AS/400

Деревья с двоичным основанием

Описанный выше метод двоичного поиска можно представить в виде древовидной структуры. Дерево будет содержать два типа узлов: тестовые и окончательные. Каждый тестовый узел дерева проверяет один разряд числа. По тому, равен разряд 1 или 0, в качестве следующего выбирается один из двух узлов следующего уровня. Начиная с вершины дерева [ 55 ] , первый узел проверяет первый разряд числа (самый левый). Второй слой дерева содержит два текстовых узла, один из которых выбирается, если первый разряд был равен 0, а другой — если первый разряд был равен 1. На третьем уровне имеется четыре узла, на четвертом — восемь и так далее вплоть до десятого узла, на котором расположено 512 тестовых узлов. Одиннадцатый уровень — последний для данного дерева и содержит 1024 окончательных узла. Окончательный узел содержит точное значение искомого числа.

55

В информатике деревья всегда растут вверх ногами. Где еще корень расположен наверху, а ветви тянутся вниз?

Итак, для поиска числа мы начинаем с вершины дерева и проверяем разряды: слева направо. На каждом уровне дерева проверяется один из разрядов. После десяти проверок мы оказываемся в одном из окончательных узлов и можем точно назвать число.

Мы только что описали двоичное дерево. Оно сбалансированное, так как присутствуют все узлы. При поиске по таблице могут присутствовать не все узлы, так как в таблице присутствуют не все возможные элементы. Следовательно, и проверяются не все разряды числа, некоторые уровни могут отсутствовать. Такое дерево в отличии от двоичного дерева, где присутствуют все узлы, называется деревом с двоичным основанием (binaryradix tree).

Использование деревьев с двоичным основанием в AS/400 для реализации машинных индексов мы рассмотрим на примере рисунка 6.4. На нем показан простой файл из девяти записей, упорядоченных в порядке поступления. Каждая запись имеет несколько полей, на рисунке показаны лишь некоторые. Одно из полей — поле имени — предназначено для использования в качестве ключа. Для файла построен индекс, который также показан на рисунке. Каждая запись индекса имеет только два поля: поле ключа и логический адрес записи. Девять элементов индекса отсортированы по порядку значений ключа. В данном случае, ключи отсортированы по алфавиту, и первым элементом является Baker, а последним Wu. Поле логического адреса записи задает относительную позицию соответствующей записи в исходном файле, логическая адресация всегда начинается с 0 (для первой записи). Элемент для Baker указывает, что запись Baker является в файле седьмой.

Файл	Индекс
Адрес
Имя	Дата рождения	Должность	Имя	логической записи 0
JONES	082140	A	BAKER	006
SMITH	122750	K	BARNS	007
WU	041259	Z	CARSON	008
MARKLY	111163	T	JOHNSON	005
PETERS	070457	C	JONES	000
JOHNSON	062753	A	MARKLY	003
BAKER	031747	C	PETERS	004
BARNS	090959	B	SMITH	001
CARSON	013147	B	WU	002

Рисунок 6.4. Пример простого файла и индекса

Точный формат логического адреса записи изменяется на AS/400 в зависимости от того, как используется индекс. Например, как уже говорилось, каждый элемент сегмента индекса области данных содержит ключ и относительный адрес, в свою очередь включающий в себя номер области данных, идентификацию сегмента области данных записей и порядковый номер записи. Данный относительный адрес уникальным образом идентифицирует запись, соответствующую ключу. В других случаях применения индекса используется иная форма относительных адресов.

Давайте с помощью этого индекса создадим дерево с двоичным основанием. На рисунке 6.5 показан индекс с рисунка 6.4 с представлением поля ключа в коде EBCDIC. Индекс представлен в шестнадцатеричной и двоичной формах. Например, первая буква имени Baker имеет шестнадцатеричное значение С2. В двоичной системе счисления С2 будет 11000010. Вторая буква имени Baker имеет шестнадцатеричное значение С1 (11000001 двоичное). Каждый ключ располагается в памяти в виде цепочки нулей и единиц, как показано на рисунке.

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

чающимся битом (сканирование всегда идет слева направо) будет пятый в третьем байте. Если в дереве только два элемента Baker и Barns, то чтобы отличить один от другого, достаточно проверить пятый разряд третьего байта. Если разряд равен 0, то это элемент Baker, а если 1, то Barns.

Допустим, теперь мы хотим добавить к дереву Carson. Тогда первым битом, отличающимся и от Baker, и от Barns, будет восьмой первого байта.

Последовательность построения дерева показана на рисунке 6.6. На первом шаге в дереве есть единственный окончательный узел для Baker. Окончательный узел содержит некоторый текст (в данном случае «Baker») и логический адрес записи 006. На втором шаге к дереву добавляется Barns. Здесь к дереву непосредственно над Baker добавляется тестовый узел для проверки пятого разряда третьего байта. Тестовый узел содержит общий текст ключей (BA) и номер бита, который должен проверяться в следующем байте. В нашем примере с двумя байтами совпадающего текста (ВА) ясно, что бит, нуждающийся в проверке, находится в следующем (третьем) байте, задавать который явно не обязательно. При выборе следующего узла всегда берется левый, если проверяемый бит равен 0, и правый — в противоположном случае. Справа от первого окончательного узла добавлен второй окончательный узел для Barns с логическим адресом записи 007. Обратите внимание, что после удаления общего текста, терминальные узлы содержат только остатки имен (KER и RNS для Baker и Barns соответственно).

Шаг 1: В дереве только BAKER

Шаг 2: Добавляем BARNES

Шаг 3: Добавляем CARSON

Рисунок 6.6. Построение дерева с двоичным основанием

На шаге 3 к дереву добавляется Carson. Создается новый тестовый узел для проверки восьмого бита первого байта. В новом тестовом узле нет общего текста. Если при проверке восьмой бит первого байта равен 0, то далее следует проверить расположенный левее тестовый узел для Baker/Barns. Если же восьмой бит первого байта равен 1, то следующим будет окончательный узел справа для Carson. Данный узел содержит текст (CARSON) и логический адрес записи 008.

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

Рисунок 6.7. Пример дерева с двоичным основанием

Любое имя в дереве может быть найдено уже описанным методом. Но как быть с именами, которых в дереве нет? Предположим, что мы пытаемся найти там имя Soltis. Проверяем третий бит первого байта и видим, что он равен 1, затем — шестой бит первого байта, который равен 0. Это приводит нас к окончательному узлу для Smith. Теперь понятна причина хранения текста в окончательных узлах — на один и тот же окончательный узел может отображаться много имен. При достижении окончательного узла необходимо сравнить хранящийся там текст с остатком имени, поиск которого мы ведем. Если они совпали — мы нашли правильный окончательный узел, если нет — искомое имя отсутствует в дереве.

Другая характеристика дерева связана со способом добавления к нему элементов. Мы всегда просматриваем строку битов для каждого нового элемента слева направо в поиске первого бита нового ключа, отличающего его от всех, уже находящихся в дереве. Таким образом, гарантируется, что при проходе по любому пути в дереве биты проверяются слева направо. В тестовом узле никогда не приходится возвращаться к началу имени: мы всегда движемся вперед.

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