Предисловие (стр. 33 )

Как и схемы базы данных других архитектурных уровней, схема хранения представляется в терминах типов, а не экземпляров объектов хранимых данных. Для ее спецификации используются специальные языковые средства. Пример глубоко проработанной концепции управления средой хранения базы данных представляет собой язык определения хранимых данных (Data Storage Definition Language), разработанный CODASYL. Нужно отметить, однако, что в современных реляционных СУБД не используются настолько тонкие механизмы управления средой хранения. Это связано с несколькими причинами. Наиболее важные из них заключаются в следующем. Во-первых, реляционные СУБД имеют дело с весьма простыми структурами хранимых данных, в отличие от более ранних систем. Во-вторых, существенно выросла скорость обмена данными между дисковой и оперативной памятью. Наконец, в современных операционных системах используются совершенно иные методы управления пространством памяти. Все эти обстоятельства позволили использовать иные подходы к механизмам СУБД, обеспечивающим управление хранимыми данными. Организация данных в среде хранения при этом в значительной мере определяется механизмами СУБД автоматически по умолчанию, в соответствии с описанием данных в концептуальной схеме базы данных.

Хранимые записи одного типа состоят из фиксированной совокупности полей, служащих для представления значений какого-либо типа (чисел, литерных строк, дат, булевских значений, денежных единиц и т. д.) и могут иметь формат фиксированной или переменной длины.

Записи переменной длины возникают, если допускается использование повторяющихся групп полей с переменным числом повторений либо строк переменной длины. Работа с хранимыми записями переменной длины существенно усложняет управление пространством памяти среды хранения. Однако необходимость их использования может быть продиктована характером модели данных концептуального уровня системы. Следует заметить, что и в таких случаях, иногда в ущерб производительности системы, отказываются для простоты от использования хранимых записей переменной длины, разбивая их на несколько записей фиксированной длины, возможно, различных типов.

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

Для обеспечения естественной структуризации хранимых данных, более эффективного управления ресурсами и/или для технологического удобства все пространство памяти базы данных обычно разделяется на части (области, разделы и т. п.). Области используются для размещения хранимых записей одного или нескольких типов и разбиваются на пронумерованные страницы фиксированного размера. На странице размещается, как правило, несколько хранимых записей.

Страницы представляются в среде операционной системы блоками внешней памяти, доступ к которым осуществляется за одно обращение. В некоторых системах размером страницы можно управлять. При этом приходится выбирать компромисс между производительностью системы и требуемым объемом оперативной памяти. В самом деле, чем больше размер страницы, тем больше записей прочитывается из внешней памяти за один доступ и тем меньше доступов требуется. Вместе с тем при большем размере страницы требуется больше оперативной памяти для буферов обмена с внешней памятью. Управление размером страницы предусматривается в некоторых СУБД, работающих на мейнфреймах. На персональных компьютерах такие возможности обычно не обеспечиваются.

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

Прямая адресация не позволяет, однако, перемещать записи внутри области без изменения их непосредственного адреса. Такие изменения привели бы к необходимости коррекции различных указателей на записи в среде хранения, что было бы чрезвычайно трудоемкой процедурой. Поэтому перемещать записи при прямой адресации нецелесообразно. В связи с этим прямой адресации, весьма эффективной с точки зрения времени доступа, сопутствует неприятное явление - фрагментация пространства страниц, препятствующая рациональному его использованию. Подобная ситуация особенно часто возникает при работе с записями переменной длины. Для преодоления указанных трудностей применяется другой вид адресации - косвенная адресация.

Один из способов реализации косвенной адресации сводится к следующему. Часть пространства каждой страницы отводится для индекса страницы. Число статей (слотов) в нем одинаково для всех страниц. Адресом записи в пространстве памяти по-прежнему служит номер этой записи в области. С помощью простых арифметических операций можно по номеру записи определить номер нужной страницы и номер требуемого слота в индексе этой страницы. Найденный слот укажет местоположение записи на странице.

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

Если запись после ее модификации не вмещается на страницу, она помещается на специально отведенные в данной области страницы переполнения, и соответствующий слот по-прежнему указывает место ее размещения.

При таком подходе становятся возможными перемещения записей на странице, позволяющие исключать фрагментацию свободного пространства, производить "сборку мусора" - возвращать освободившееся пространство для повторного использования. Важно при этом, что приложения базы данных остаются нечувствительными к таким операциям. Косвенная адресация хранимых записей является, таким образом, одной из составных частей комплекса методов и инструментария, используемого в СУБД для обеспечения "физической" независимости данных.

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

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

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

Имеются ситуации, когда место размещения несущественно, но важна точка включения записи в упорядоченную последовательность уже содержащихся в базе данных хранимых записей. С такой ситуацией приходится иметь дело в системах типа КОДАСИЛ при запоминании записи ­обязательного члена набора. Тогда запись запоминается в любом свободном месте, желательно - на страницах, где хранятся ее непосредственные соседи или запись-владелец набора, и с помощью указателей включается в упорядоченную цепочку записей - участников набора.

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

Более сложные механизмы размещения используются при ассоциативном доступе к хранимым записям, предполагающем определение местоположения записи по значениям содержащихся в ней данных. При этом некоторая комбинация полей записи служит ее идентификатором (ключом). По значению ключа и определяется место размещения записи. Для этой цели используются различные методы отображения ключа в адрес. Наиболее популярными среди них являются методы хеширования (перемешивания). Рассмотрим схематично суть этих методов.

Пусть число возможных значений ключа не превышает некоторого числа N. Тогда каждому значению ключа поставим в соответствие значение случайного числа, равномерно распределенного в интервале [0, N-1]. Это число называют сверткой ключа, и оно принимается за адрес рассматриваемой записи. Для генерации таких чисел на основе значений ключей используют специально подобранные функции, называемые функциями хеширования.

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

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

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