Внутренняя форма хранения дерева с двоичным основанием оптимизирована как с точки зрения производительности, так и занимаемого пространства. Первая базовая структура для дерева с двоичным основанием была создана инженером Филом Хо-вардом (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, используя данные совместно с остальными приложениями. В будущем эти возможности станут еще более значимы.

Интегрированная защита AS/400 защищает базу данных и другие компоненты системы от несанкционированного доступа и предотвращает разрушение данных. В следующей главе, мы рассмотрим эту интегрированную защиту, а также управление доступом в SLIC.

Хакеры и вирусы на AS/400? Это невозможно. Они пиратствуют только на Unix и ПК.

Я вспоминаю фильм «Парк юрского периода», в конце которого девочка подходит к компьютеру, на котором была совершена диверсия, приведшая к выходу динозавров на свободу. «Это Unix!» — восклицает она, вскрывает его защиту и немедленно устраняет неполадки. Тут я сказал про себя: «Конечно, чего же Вы хотели от Unix». А в фильме «День независимости» вирус был запущен в компьютер космического корабля пришельцев. Большинство зрителей до этого и не подозревали, что инопланетяне используют компьютеры Apple Macintosh. Но, слава Богу, это оказалось именно так, вирус сработал, и наш мир был спасен.

Вообще, в фильмах часто злодеи проникают в чужие компьютеры, или недовольный сотрудник внедряет вирус в компьютерную сеть фирмы. Приятно сознавать, что ничего подобного на AS/400 произойти не может. Или все-таки может?

Как и многие другие функции, в AS/400, в отличие от большинства иных систем, защита была встроена с самого начала, а не добавлена уже после создания,. Однако никакие средства защиты не помогут, если их не использовать, а многие пользователи AS/400 так и делают. Например, в среде клиент/сервер необходимо принимать специальные меры для защиты данных AS/400 от незащищенных клиентов, таких как Windows 95 и Windows NT. Более того, в современном сетевом мире многие AS/400 подключены к Интернету, в этом случае также следует применять определенные средства защиты информационных ресурсов. По счастью, интегрированные средства защиты AS/400 обеспечивают крепкий фундамент безопасности всей системы. В этой главе мы рассмотрим средства защиты AS/400 и обсудим, как лучше использовать их.

В прошлом защитить вычислительную систему было относительно легко. Обычно, было достаточно вставить замок в дверь машинного зала и заставить конечных пользователей вводить при входе в систему пароль. Современный мир уже не так прост. Наибольшей степени опасности подвергаются AS/400, включенные в вычислительную сеть: во внутрифирменную ЛВС или в глобальную сеть, например в Интернет. В любом случае, AS/400 предоставляет средства для минимизации или полного устранения риска несанкционированного доступа. Проблемы защиты вычислительной системы очень похожи на те, что возникают при защите дома или автомобиля: Вы должны правильно рассчитать соотношение цены и допустимой степени риска.

Очевидно, что в разных ситуациях AS/400 нужен разный уровень защиты. У пользователя должна быть возможность самостоятельного выбрать этот уровень. Хорошая система защиты разработана так, чтобы компьютер мог работать вообще без защиты, с ограниченной защитой или с полной защитой, но во всех случаях система защиты должна быть активна.