Фрэнк Солтис - Основы AS/400

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

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

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

Элемент дерева можно также удалить. Это простая операция, так как на окончательный узел может указывать один и только один тестовый узел. Возьмите имя, подлежащее удалению, отыщите в дереве соответствующий ему окончательный узел, удалите его, вернитесь к расположенному выше тестовому узлу и объедините его со вторым окончательным узлом в новый окончательный узел.

Внутренняя форма хранения дерева с двоичным основанием оптимизирована как с точки зрения производительности, так и занимаемого пространства. Первая базовая структура для дерева с двоичным основанием была создана инженером Филом Хо-вардом (Phil Howard) в 70-х годах. В его схеме правый и левый потомки тестового узла вместе с возможным общим текстом объединены в кластер. Такие кластеры располагались в памяти один за другим, и для ссылки на кластер использовалось его положение в цепочке. Это устраняло необходимость учета адресов для ссылки на следующий узел.

Фил изобрел очень элегантный механизм перемещения от одного узла дерева к другому. Кластер не содержал адресов следующего или предыдущего узла. Вместо этого, их положения определялись с помощью операции XOR, что позволяло перемещаться по дереву в обоих направлениях. Этим достигалась еще и экономия памяти, поскольку не нужно было хранить прямые и обратные ссылки на предыдущие и последующие узлы.

Чтобы найти следующий узел дерева, операция XOR выполняется над значением, хранящимся в текущем узле, и позицией предыдущего узла. Ясно, что значение, хранящееся в текущем узле, — результат XOR над позициями следующего и предыдущего узлов. Таким образом, чтобы вычислить местоположение следующего узла, нужно знать лишь текущее значение и позицию предыдущего узла. Предположим, что мы хотим пройти по дереву в обратном направлении. Выполнив операцию XOR над значением в текущем узле и позицией следующего узла, мы получаем позицию предыдущего узла. Таким образом, из любой точки дерева, зная предыдущую, текущую и следующие позиции, а также содержимое текущего узла, можно перемещаться вверх и вниз без ссылок. Для хранения нужных нам трех позиций годится простой стек.

Реализация дерева с двоичным основанием минимизирует число страничных ошибок путем разделения дерева на поддеревья. Формально, такую структуру следовало бы называть фрагментированным деревом с двоичным основанием. При переполнении страницы, выше по дереву выполняется разделение, и к индексу добавляются новые поддеревья.

Предположим, мы решили разделить дерево из нашего примера на рисунке 6.7. Разумно поместить на одну страницу все терминальные узлы от Baker до Peters вместе с их тестовыми узлами, а на вторую — терминальные узлы от Smith до Wu, а также один указывающий на них тестовый узел.