Основы AS/400
Шрифт:
Шаг 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. Теперь понятна причина хранения текста в окончательных узлах — на один и тот же окончательный узел может отображаться много имен. При достижении окончательного узла необходимо сравнить хранящийся там текст с остатком имени, поиск которого мы ведем. Если они совпали — мы нашли правильный окончательный узел, если нет — искомое имя отсутствует в дереве.
Другая характеристика дерева связана со способом добавления к нему элементов. Мы всегда просматриваем строку битов для каждого нового элемента слева направо в поиске первого бита нового ключа, отличающего его от всех, уже находящихся в дереве. Таким образом, гарантируется, что при проходе по любому пути в дереве биты проверяются слева направо. В тестовом узле никогда не приходится возвращаться к началу имени: мы всегда движемся вперед.
Метод, используемый для вставки элементов, также гарантирует, что дерево всегда будет иметь одну и ту же конфигурацию, независимо от порядка добавления элементов. Более того, окончательные узлы всегда упорядочены в соответствии со значениями ключей слева направо. В нашем примере, окончательные узлы расположены в алфавитном порядке имен в ключевом поле. Это не случайность, а свойство дерева. Дерево само по себе обеспечивает логическую последовательность ключей, так что сортировка физических записей не нужна.
Элемент дерева можно также удалить. Это простая операция, так как на окончательный узел может указывать один и только один тестовый узел. Возьмите имя, подлежащее удалению, отыщите в дереве соответствующий ему окончательный узел, удалите его, вернитесь к расположенному выше тестовому узлу и объедините его со вторым окончательным узлом в новый окончательный узел.
Внутренняя организация дерева с двоичным основанием
Внутренняя форма хранения дерева с двоичным основанием оптимизирована как с точки зрения производительности, так и занимаемого пространства. Первая базовая структура для дерева с двоичным основанием была создана инженером Филом Хо-вардом (Phil Howard) в 70-х годах. В его схеме правый и левый потомки тестового узла вместе с возможным общим текстом объединены в кластер. Такие кластеры располагались в памяти один за другим, и для ссылки на кластер использовалось его положение в цепочке. Это устраняло необходимость учета адресов для ссылки на следующий узел.
Фил изобрел очень элегантный механизм перемещения от одного узла дерева к другому. Кластер не содержал адресов следующего или предыдущего узла. Вместо этого, их положения определялись с помощью операции XOR, что позволяло перемещаться по дереву в обоих направлениях. Этим достигалась еще и экономия памяти, поскольку не нужно было хранить прямые и обратные ссылки на предыдущие и последующие узлы.
Чтобы найти следующий узел дерева, операция XOR выполняется над значением, хранящимся в текущем узле, и позицией предыдущего узла. Ясно, что значение, хранящееся в текущем узле, — результат XOR над позициями следующего и предыдущего узлов. Таким образом, чтобы вычислить местоположение следующего узла, нужно знать лишь текущее значение и позицию предыдущего узла. Предположим, что мы хотим пройти по дереву в обратном направлении. Выполнив операцию XOR над значением в текущем узле и позицией следующего узла, мы получаем позицию предыдущего узла. Таким образом, из любой точки дерева, зная предыдущую, текущую и следующие позиции, а также содержимое текущего узла, можно перемещаться вверх и вниз без ссылок. Для хранения нужных нам трех позиций годится простой стек.
Реализация дерева с двоичным основанием минимизирует число страничных ошибок путем разделения дерева на поддеревья. Формально, такую структуру следовало бы называть фрагментированным деревом с двоичным основанием. При переполнении страницы, выше по дереву выполняется разделение, и к индексу добавляются новые поддеревья.
Предположим, мы решили разделить дерево из нашего примера на рисунке 6.7. Разумно поместить на одну страницу все терминальные узлы от Baker до Peters вместе с их тестовыми узлами, а на вторую — терминальные узлы от Smith до Wu, а также один указывающий на них тестовый узел.
Однако, здесь нас подстерегает неприятность. В узлах нет адресов для связи с другими узлами — вместо этого используются относительные номера позиций. Чтобы попасть на другую страницу памяти, необходим адрес. Решение состоит в создании узла нового типа, который будет содержать адрес и позволит ссылаться на другую страницу дерева. Если верхний узел нашего примера — корневой узел — поместить на третью страницу и разместить в нем указатели на две другие, то мы получим фраг-ментированное дерево. Верхние узлы на всех трех страницах теперь являются корневым узлами для своих страниц, и мы значительно увеличили максимальный объем памяти, которая может использоваться для хранения данного дерева.
Другое преимущество фрагментирования — то, что, попав в процессе поиска на некоторую страницу памяти, содержащую фрагмент дерева, мы остаемся на ней на всех уровнях тестирования. Перед переходом на следующую страницу все тестовые узлы данной страницы на пути поиска будут просмотрены. Кроме того, поскольку для поиска в очень больших индексах требуется относительно немного проверок (вспомните, что при поиске в индексе из миллиона записей требуется, в среднем, только 20 проверок), то лишь в редких случаях придется затронуть более одной-двух страниц. В результате, данная схема обеспечивает наивысшую производительность по сравнению со всеми иными известными схемами индексации.
Выводы
Интегрированная база данных дает AS/400 целый ряд преимуществ, обеспечивая недостижимый для других систем уровень эффективности и производительности. Многие из этих преимуществ были нами рассмотрены. Так как база данных AS/400 не «сидит» поверх ОС, ею могут пользоваться все компоненты системы. База данных AS/ 400 не изолирована от других компонентов, как на обычных системах.
База данных AS/400 позволяет приложениям, написанным для различных интерфейсов, сосуществовать и работать с одними и теми же данными, обеспечивая непосредственную реализацию на AS/400 внешних интерфейсов и инструментария других баз данных. Следовательно, и приложения, написанные для иных баз данных, уже сейчас могут работать прямо на AS/400, используя данные совместно с остальными приложениями. В будущем эти возможности станут еще более значимы.