Распределенная обработка данных. Найханова Л.В. - 70 стр.

функции свертки (хэш-функции), вырабатывающей значение меньшего размера. Свертка
значения ключа затем используется для доступа к записи.
     В самом простом, классическом случае, свертка ключа используется как адрес в
таблице, содержащей ключи и записи. Основным требованием к хэш-функции является
равномерное распределение значение свертки. При возникновении коллизий (одна и та же
свертка для нескольких значений ключа) образуются цепочки переполнения. Главным
ограничением этого метода является фиксированный размер таблицы. Если таблица
заполнена слишком сильно или переполнена, но возникнет слишком много цепочек
переполнения, и главное преимущество хэширования - доступ к записи почти всегда за
одно обращение к таблице - будет утрачено. Расширение таблицы требует ее полной
переделки на основе новой хэш-функции (со значением свертки большего размера).
     В случае баз данных такие действия являются абсолютно неприемлемыми. Поэтому
обычно вводят промежуточные таблицы-справочники, содержащие значения ключей и
адреса записей, а сами записи хранятся отдельно. Тогда при переполнении справочника
требуется только его переделка, что вызывает меньше накладных расходов.
     Чтобы избежать потребности в полной переделки справочников, при их организации
часто используют технику B-деревьев с расщеплениями и слияниями. Хэш-функция при
этом меняется динамически, в зависимости от глубины B-дерева. Путем дополнительных
технических ухищрений удается добиться сохранения порядка записей в соответствии со
значениями ключа. В целом методы B-деревьев и хэширования все более сближаются.
Журнальная информация
     Структура журнала обычно является сугубо частным делом конкретной реализации.
Мы отметим только самые общие свойства.
     Журнал обычно представляет собой чисто последовательный файл с записями
переменного размера, которые можно просматривать в прямом или обратном порядке.
Обмены производятся стандартными порциями (страницами) с использованием буфера
оперативной памяти. В грамотно организованных системах структура (и тем более,
смысл) журнальных записей известна только компонентам СУБД, ответственным за
журнализацию и восстановление. Поскольку содержимое журнала является критичным
при восстановлении базы данных после сбоев, к ведению файла журнала предъявляются
особые требования по части надежности. В частности, обычно стремятся поддерживать
две идентичные копии журнала на разных устройствах внешней памяти.


     Распределенная система управления базами данных System R*
     Основную цель проекта можно сформулировать следующим образом: обеспечить
средства интеграции локальных баз данных System R, располагающихся в узлах
вычислительной сети, с тем, чтобы пользователь, работающий в любом узле сети, имел
доступ ко всем этим базам данных так, как если бы они были централизованы. При этом
должны обеспечиваться:
     - легкость использования системы;
     - возможности автономного функционирования при нарушениях связности сети
        или при административных потребностях;
     - высокая степень эффективности.
     Для решения этих проблем было необходимо принять ряд проектных решений,
касающихся декомпозиции исходного запроса, оптимального выбора способа выполнения
запроса, согласованного выполнения транзакций, обеспечения синхронизации,
обнаружения и разрешения распределенных тупиков, восстановления состояния баз
данных после разного рода сбоев узлов сети.
     Легкость использования системы достигается за счет того, что пользователи System
R* (разработчики прикладных программ и конечные пользователи) остаются в среде

70