8.Тиори Т., Фрай Дж. Проектирование структур баз данных : в 2 кн. Кн. 1 / под ред. В. И. Скворцова ; пер. с англ. А. И. Роговского. — М. : Мир, 1985. — 287 с.

9.Ульман Дж. Д. Теория проектирования реляционных баз данных / пер. с англ. М. Р. Когаловского, В. В. Когутовского // Основы систем баз данных (глава 5) / под ред. М. Р. Когаловского. — М. : «Финансы и статистика», 1983.

§8. Основные принципы хранения данных во внешней памяти

Для функционирования реляционной СУБД возникает необходимость хранить следующие разновидности объектов базы данных во внешней памяти:

1.кортежи отношений — основная часть базы данных, большей частью непосредственно видимая пользователям;

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

3.журнальную информацию, поддерживаемую для удовлетворения потребности в надежном хранении данных (откаты, восстановление);

4.служебную информацию, поддерживаемую для удовлетворения внутренних потребностей нижнего уровня системы.

Существуют два принципиальных подхода к физическому хранению отношений:

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

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

Везде далее будет будет рассмотрен только покортежный подход в силу его большей распространенности.

В книге [1] на стр. 291 представлена сводная таблица сравнения различных способов хранения отношений, чему посвящен весь его раздел 8.4.

8.1. Страничная организация хранения данных

Определение 1. Страницей (физической записью, блоком) называется физическая единица обме-

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

идля извлечения этой страницы запрашивает диспетчер дисков.

•Диспетчер накопителей определяет физиче-

ское положение искомой страницы на диске

ипосылает соответствующий вопрос на вводвывод данных.

Страницы в целях адресации содержимого можно разбить на слоты, каждый из которых содер-

жит по одному кортежу. Тогда адрес записи (tid — tuple id) можно представить в виде парыpage_id; slot 1, где page_id — идентификатор страницы, а slot — номер слота, содержащего запись (кортеж).

Заголовок страницы содержит информацию о физическом дисковом адресе страницы, которая логически следует за данной страницей (указатель на рис. 4а).

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

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

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

Обычно каждый кортеж хранится целиком в одной странице, т. е. максимальная длина кортежа любого отношения ограничена размерами страницы. Возникает вопрос: как быть с «длинными» данными, которые в принципе не помещаются в одной странице? Применяются несколько методов.

•Наиболее простым решением является хранение таких данных в отдельных (вне базы данных) файлах с заменой «длинного» данного в кортеже на имя соответствующего файла.

1 Существует и альтернативный способ адресации — ставить в соответсветствие каждой записи свой уникальный целочисленный номер, а также использовать таблицу, хранящую информацию о местоположении каждой записи (страница

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

48

•В некоторых системах (например, в СУБД Informix) такие данные хранились в отдельном наборе страниц внешней памяти, связанном физическими ссылками. Оба эти решения сильно ограничивают возможность работы с длинными данными (как, например, удалить несколько байтов из середины 2-мегабайтной строки?).

•Все чаще используется метод, когда «длинные» данные организуются в виде B-деревьев последовательностей байтов.

8.2. Управление буферами внутренней памяти

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

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

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

–по запросу (пока нет обращения, страница не загружается): достоинством является экономия памяти, а недостатком — при возникновении запроса теряется время в ожидании подкачки.

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

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

1. Выталкивание случайной страницы.

2. Принцип FIFO (first in, first out). Выталкивается первая пришедшая, т. е. дольше всего находящаяся в памяти страница.

3. LRU (Least Recently Used). Выталкивается страница, дольше всего не использовавшаяся. 4. Циклическое выталкивание (clock replacement)представляет все страницы во внутренней памяти в виде замкнутого однонаправленного списка. В соответствие каждой странице ставится битовый флаг (page reference bit). При попадании страницы в кэш, битовый флаг устанавливается в значение 0 и страница помещается в хвост списка. В случае обращения к странице, ее битовый флаг устанавливается в значение 1. При необходимости выталкивания страницы из внутренней памяти, производится цикличный просмотр списка страниц в памяти, начиная с текущей страницы (header page). Если битовый флаг очередной

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

5.MRU (Most Recently Used). Выталкивается страница, наиболее недавно (только что) использовавшаяся.

6.NUR (Not Used Recently). Выталкивается страница, не использовавшаяся недавно. Для отслеживания времени необходимы всего 2 бита признака: обращения (нуль, если не было обращений), модификации (нуль, если страница не изменялась). Выталкивается страница с минимальным значением этой пары бит. Вариант сочетания битов 01 соответствует

49