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

Журналы SLIC

Ранее мы рассматривали ведение журналов базы данных. Базовые функции для протоколирования изменений базы данных реализованы ниже MI. Соответствующая поддержка предоставляется двумя системными объектами MI: порт журнала и область журнала. Порт журнала управляет определением журнала, а область журнала представляет собой контейнер для записей в него. Эти два объекта поддерживают объекты OS/400 журнал и приемник журнала соответственно. Обратите внимание, что на границе MI имена снова меняются.

Порт журнала, как и почти все другие системные объекты, состоит из двух сегментов. Базовый сегмент содержит адреса объектов, для которых ведется журнал, а также адреса текущих журнальных пространств. Компонент базы данных, реализованный в OS/400, использует сегмент ассоциированного пространства.

Область журнала — это специальный системный объект MI, состоящий из множества сегментов. Базовый сегмент содержит адреса порта журнала, а также адреса до 120 сегментов данных журнала. Сегмент данных журнала — это сегмент еще одного типа, который может быть частью системного объекта «область журнала». В сегментах данных журнала хранятся записи журнала.

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

Управление транзакциями в SLIC

Ранее мы обсуждали базовые функции подтверждения и отката изменений. Эти функции поддерживаются и в MI, и в компоненте базы данных на уровне SLIC. В MI такую поддержку предоставляет системный объект блок транзакции (commit block). Он фиксирует изменения объекта, участвующего в транзакции. Блоки транзакции связаны с процессами.

Объекты добавляются к блоку транзакции и удаляются из него. Блок транзакции также содержит информацию о блокировках записей. Эти блокировки освобождаются командой MI <<Cornrnrt>>. Команда <<Decornrnrt>>, которая практически во всех ЯВУ (включая набор команд OS/400) называется «Rollback», откатывает все изменения, сделанные в процессе транзакции, освобождает блокировки и устанавливает курсор в положение, нормальное на момент начала транзакции.

Машинные индексы

Перейдем к последней теме, связанной с нижним уровнем поддержки базы данных в AS/400 — к индексам. Мы уже обсуждали два вида индексов: независимый (в главе 5) и индекс области данных (в этой главе). Повторю, что оба этих системных объекта содержат дерево с двоичным основанием.

Итак, что такое индекс? На мой взгляд, наиболее удачное определение таково: индекс — организованный набор информации для быстрого поиска в наборе элементов, например в большой таблице. Индексация играет важную роль в реализации многих компонентов AS/400 и любой другой системы. Поэтому еще при проектировании System/38 было принято решение встроить ниже MI максимально эффективный индекс таким образом, чтобы все системные компоненты могли при необходимости использовать его, а не создавать свои собственные. Этот встроенный индекс и называется машинным индексом.

Машинный индекс полезен различным компонентам AS/400 при поиске в таблицах, адресации областей, сортировке и т. д. База данных применяет его при индексации области данных, работе со списком транзакций журнала и т. п.; компонент управление памятью — для многих своих справочников. Машинные индексы используются и в контекстах, и для поиска прав доступа. OS/400 использует объекты типа «независимый индекс» для нескольких целей, включая обработку сообщений, защиту

и спулинг.

Основные характеристики машинного индекса таковы:

обеспечивает обобщенный поиск, позволяя находить группы связанных элементов;

управляет используемым пространством;

позволяет минимизировать случаи отсутствия нужной страницы в памяти (страничные ошибки);

поддерживает ключи переменной длины до 2048 байтов;

использует алгоритм двоичного поиска;

хранит элементы в виде фрагментированного дерева с двоичным основанием (подробнее — в разделе «Внутренняя организация дерева с двоичным основанием» этой главы).

Двоичный поиск

Проще всего понять, что такое двоичный поиск, можно на примере игры в угадывание чисел. Смысл игры в том, что один игрок задумывает число внутри некоторого диапазона, например между 1 и 1000, а второй — пытается угадать это число за минимально возможное количество попыток. При каждой попытке второму игроку сообщается, является ли названное им число большим, меньшим или равным задуманному.

Прием быстрого угадывания чисел в этой игре основан на двоичной системе счисления. Чтобы угадать число между 1 и 1000, при первой попытке следует назвать 512 (29 = 512). Если нам скажут, что это число слишком велико, то задуманное число больше нуля и меньше 512, поэтому далее мы называем 256 (28= 256) — следующую меньшую степень двойки. Если же сказано, что названное число меньше задуманного, то задумано число большее 512 и для следующей попытки нужно прибавить 256 к 512 и назвать 768, и при каждой следующей попытке прибавлять следующую меньшую степень двойки. Если названное число больше задуманного, мы вычитаем эту степень двойки и прибавляем следующую меньшую степень.

Предположим, что первый игрок задумал 700. Отгадывающему следует называть такую последовательность чисел: 512, 768, 640, 704, 672, 688, 696 и, наконец, 700. При этом ему будет сообщаться, что первое число меньше, второе больше, третье меньше и т. д. На основании этой информации он будет вычислять следующее значение и, в конце концов, задуманное число будет отгадано за восемь попыток.

Если мы посмотрим на последовательность ответов первого «больше/меньше» из приведенного примера, то заметим интересную закономерность. Эта последовательность выглядит так: «меньше», «больше», «меньше», «больше», «меньше», «меньше», «меньше» и «равно». Если на место каждого ответа «больше» подставить 0, а на место каждого ответа «меньше» — 1, то мы получим двоичное число. Учитывая, что для задания любого числа между 1 и 1000 требуется 10 разрядов, можно представить 700 как 1010111100. Мы угадали это число, двигаясь слева направо и используя ответы «больше/меньше» для определения двоичной цифры в текущей позиции.

С использованием данного метода задуманное число всегда может быть найдено не более чем за 10 попыток. В нашем примере потребовалось только восемь попыток,так как число делится на 4 — степень двойки. Обратите внимание, что любое нечетное число потребует 10 попыток, по одной на разряд. Максимальное число попыток можно вычислить как логарифм 1000 по основанию 2. Иначе это значение можно определить, учитывая, что 2 = 1024. Для угадывания числа между единицей и миллионом по данному методу требуется лишь 20 или менее попыток. Приведенный пример иллюстрирует алгоритм двоичного поиска, который применяется для нахождения элемента индекса.

Структура, в которой все записи заполнены, считается сбалансированной. При поиске по сбалансированному индексу с n элементами требуется выполнить сравнение лишь для log2 n элементов. Наш пример с угадыванием чисел был сбалансированным, так как в последовательности присутствуют все числа. Но даже для сильно несбалансированных структур среднее число попыток возрастает менее чем на 10 процентов. Алгоритм двоичного поиска отлично работает для большого числа элементов, но обычно не рекомендуется, если их число меньше 50.

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

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

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