Лекция 20
dBase, MS SQL, Oracle
20.1. Физическая структура данных в dBase
Dbase-подобная
база данных физически может состоять из специализированных файлов следующего
назначения (слайд 2):
-
основного файла базы данных;
-
memo-файла
для хранения длинных полей;
-
индексного файла.
20.1.1. Структура основного файла
базы данных (типа .DBF)
Файл базы данных состоит из записи
заголовка и записей с данными. В записи заголовка, начинающейся с нулевой
позиции, определяется структура базы данных (слайд 3).
Количество полей определяет число
подзаписей полей. В базе данных для каждого поля существует одна подзапись поля
(слайд 4).
Записи с данными следуют за
заголовком и включают в себя фактическое содержимое полей. Длина записи (в
байтах) определяется суммированием длин полей, указанных в заголовке.
Записи данных (значений полей) в
файле начинаются с позиции, указываемой в записи заголовка в байтах 08-09.
Записи начинаются с байта, содержащего признак удаления. Если в этот байт
занесен пробел, то запись не удалялась; если же в первом байте – звездочка, то
запись удалена. За признаком удаления следуют данные из полей, названия которых
находятся в подзаписях полей.
20.1.2. Структура memo-файла (тип
.FPT)
Файл типа memo
содержит одну запись заголовка файла и произвольное число блоков данных (слайд
5).
В записи заголовка располагается
указатель на следующий свободный блок и размер блока в байтах, который
устанавливается командой SET BLOCKSIZE (или фиксированная длина 512 байт для
файлов типа .DBT) при создании файла. Запись заголовка начинается
с нулевой позиции файла и занимает 512 байтов.
За записью заголовка следуют блоки, в которых содержатся заголовок
блока и текст memo. В файл базы данных включены
номера блоков, которые используются для ссылки на блоки memo.
Расположение блока в memo-файле определяется умножением номера блока на размер
блока (находящийся в записи заголовка). Все memo-блоки начинаются с четных адресов
границ блоков.
20.1.3. Структура индексного файла
(тип .IDX)
В индексных файлах располагается одна
запись заголовка и одна или больше записей вершин. В записи заголовка находится
информация о корневой вершине, текущем размере файла, длине ключа, особенностях
индекса и сигнатура, а также представление ключа в коде ASCII, которое можно
вывести на печать, и выражения FOR. Запись заголовка начинается с нулевой
позиции файла (слайд 6).
Во всех других записях вершин
содержится атрибут, количество существующих ключей и указатели на вершины,
располагающиеся слева и справа (на том же уровне) от данной вершины (слайд
7, 8). Помимо этого, в них находится группа символов, представляющая
значение ключа, и либо указатель на вершину нижнего уровня, либо подлинный
номер записи в базе данных. Размер каждой записи равен 512 байтам.
20.2. Физическая структура данных в MS SQL Server
Здесь приводится схематичное описание структур данных, характерных
для MS SQL Server 7.0. Файлы операционной системы в
MS SQL Server представляются как нумерованные устройства для
хранения БД. Каждое устройство разбивается на виртуальные страницы по 8 Кбайт.
MS SQL Server используется следующая иерархия
понятий (слайд 9):
База данных – некоторый объем файлового физического
пространства для размещения данных, принадлежащих одной логической базе.
Файлы БД. Каждая база данных состоит не менее чем из двух файлов.
Один из них отводится под журнал транзакций. Отдельный файл данных может
принадлежать только одной базе данных.
Экстент. Пространство для хранения объектов выделяется блоками (экстентами)
по 8 следующих друг за другом страниц размером 8К. Экстент является единицей
выделения пространства. Поэтому при создании БД нужно указывать размер файла с
точностью до 64Кбайт.
Страница. Файлы делятся на страницы размером по 8 Кбайт каждая.
Логический номер страницы складывается из внутреннего номера базы данных,
номера файла и номера страницы в файле. В рамках БД файлы нумеруются, начиная с
1, и так же нумеруются страницы в рамках файла.
Используется два типа экстентов: однородные и смешанные.
Однородные экстенты всегда принадлежат только одному объекту. Смешанный экстент
может использоваться несколькими объектами.
В SQL Server существуют несколько
типов страниц (слайд 10).
Следующие типы страниц относятся к хранению и поиску
информации:
- страницы данных;
- индексные страницы;
- текстовые страницы;
- страницы журнала
транзакций;
Кроме этого используются также страницы размещения:
- карты распределения
блоков (основная и вторичная);
- карты свободного
пространства;
- индексные карты
размещения.
На странице всегда (в отличие от экстента) хранится
однородная информация. Все страницы имеют заголовок, в котором хранится
общая информация, используемая ядром СУБД для работы со страницами (слайд
11):
- номер страницы в формате
<номер файла, номер страницы>;
- идентификатор объекта,
которому принадлежит страница;
- индекс и уровень внутри
индексного дерева, которому принадлежит страница;
- количество строк на
странице;
- общий объем свободного
пространства на странице;
- указатель на свободное
пространство после последней строки на странице;
- минимальная длина строки
на странице;
- объем зарезервированного
пространства.
После заголовка следует информация о статусе страницы в
картах распределения блоков и карте свободного пространства.
20.2.1. Страницы размещения (слайд 12)
SQL Server
использует три типа страниц размещения: карты распределения экстентов, карты
свободного пространства, индексные карты размещения.
20.2.2. Карты
распределения экстентов
Карта распределения экстентов состоит из стандартного
заголовка и битового массива в 64 000
битов. Каждый бит характеризует один экстент. Поэтому одна страница карты распределения
описывает пространство в 64 000 экстентов или 4 Гбайт данных.
При отведении пространства используются два
типа карт распределения экстентов:
- глобальная карта
распределения (Global allocation map, GAM)
хранит информацию об использовании экстентов. Если бит
установлен в 0, то экстент занят данными, если в 1 – то экстент свободен;
- вторичная глобальная
карта распределения (Secondary global allocation map, SGAM)
хранит информацию о типе экстентов. Если бит
установлен в 1, то соответствующий экстент смешанный и минимум одна страница в
нем свободна, в остальных случаях бит равен 0.
20.2.3. Карты
свободного пространства
Карта свободного пространства (Page free space page, PFS)
отражает степень заполнения страниц. Каждая PFS-страница хранит
информацию о 8000 страницах - по одному байту на страницу. Каждый байт
представляет собой битовую карту, которая сообщает о степени занятости страницы
и о том, принадлежит ли она объекту.
Карта распределения размещается с первой страницы файла БД.
Страницы повторяются через каждые 8000 страниц.
Первая страница PFS после стандартного заголовка
страницы содержит заголовок файла (его описание), затем размещается
сам блок PFS. Вторая страница – это GAM, третья – SGAM.
Карты распределения экстентов повторяются через каждые 512 000 страниц.
20.2.4. Карты размещения
Для организации связи между экстентами и расположенными на
них объектами используются индексные карты размещения (Index Allocation Map, IAM).
Каждая таблица или индекс имеют одну или более страниц IAM. В каждом файле, в
котором размещаются таблица или индекс, существует минимум одна карта
размещения для этой таблицы или индекса. Страницы IAM размещаются произвольно
внутри файла и отводятся по мере необходимости. IAM
объединены друг с другом в цепочку двунаправленными ссылками. Указатель на первую
карту размещения содержится в поле FirstlAM системной таблицы Sysindex.
Каждая IAM описывает некоторый
диапазон экстентов и представляет собой битовую карту: если бит
установлен в 1, то в данном экстенте есть страницы, принадлежащие данному
объекту, если в 0 – то нет.
Все страницы размещения не связаны напрямую с некоторым
объектом БД, они соответствуют некоторой системной информации, поэтому параметр
«идентификатор объекта» для всех этих страниц одинаков и равен 99.
20.2.5. Страницы
данных (слайд 13)
Страницы данных используются для хранения собственно данных.
Структурно страницу данных можно подразделить на три зоны: заголовок, строки
данных и таблицу размещения строк (слоты). Связь между страницами и объектами
реализует специальная структура – карты размещения.
Строка данных должна полностью умещаться на странице, поэтому
существуют ограничения на длину строки. Размер страницы 8 Кбайт, 96 байт
занимает заголовок. Кроме того, в таблице размещения каждому слоту отводится по
4 байта для каждой строки, размещенной на странице.
Строки данных на странице не обязательно хранятся непрерывно.
При удалении строки пустое пространство помечается как свободное и потом его
может занять новая строка, перемещения строк не происходит. Адрес (смещение) на
странице и длина строки фиксируется в слоте (Slot).
Если таблица не имеет кластеризованного
индекса, то номер слота является идентификатором строки, пока не будет удалена
соответствующая строка. Если же таблица имеет кластеризованный
индекс, то слоты располагаются в порядке, задаваемом индексом.
Первые страницы данных таблиц БД расположены не подряд: сразу за первой
страницей данных таблицы следует ее индексная карта размещения.
Для более эффективного
управления дисковым пространством SQL Server не выделяет создаваемым таблицам
сразу целый экстент. Для новой таблицы или индекса, как правило, выделяется
место на смешанном экстенте. Когда объем таблицы или индекса увеличивается до
восьми страниц, все последующие выделяемые экстенты будут однородными. Соответственно,
если на смешанных экстентах места нет, а объем таблицы не
достиг еще восьми страниц, то выделяемый новый экстент будет объявлен
смешанным. Например, таблица занимает две страницы на смешанном экстенте, и в
нее еще добавляется сразу шесть записей, то если свободных страниц на смешанных
экстентах нет, будет выделен новый смешанный экстент, и на нем разместятся 6
записей. Потом, если добавляется еще одна запись, будет выделен полный новый
однородный экстент, и на нем размещена эта новая запись.
20.2.6. Строки
данных
Данные хранятся на страницах в виде строк. Каждая строка
кроме собственно данных хранит дополнительную форматирующую информацию. Длина
строки зависит от типов полей таблицы. Независимо от объявления, каждая строка
имеет поле с количеством полей переменной длины (к ним относятся также поля
фиксированной длины, допускающие неопределенные значения NULL,
которые при этом резервируют пространство, указанное в определении поля).
Фиксированные поля вместе с описателями хранятся до полей
переменной длины. Поля фиксированной длины всегда занимают свою полную длину,
значение NULL задается специальным флагом.
В каждой строке хранится общая длина строки и текущие длины
полей переменной длины. Данные считываются последовательно с начального адреса.
Вторая часть – это необязательная область, она существует
только тогда, когда имеются в записи поля переменной длины, и включает:
- указатель на
местоположение полей переменной длины;
- собственно значения полей переменной длины.
20.2.7. Текстовые
страницы
Текстовая страница может содержать несколько текстовых полей.
Строка данных содержит указатель на корневую структуру.
Собственно данные хранятся в виде сбалансированного В-дерева.
Данные длиной менее 64 байт хранятся в корневой структуре.
Для данных до 32 Кбайт корневая структура может адресовать 4
блока данных (это не экстенты страниц) до 8 Кбайт каждый. Блоки наращиваются до
8 Кбайт (реально на одной текстовой странице может быть размещено до 8080
байт).
Если же длина текстового поля более 32 Кбайт, то строятся
промежуточные узлы.
20.2.8. Индексы (слайд 14)
Кластерный
индекс представляет
собой двоичное дерево, в котором на
нулевом уровне (уровне листьев) содержатся страницы актуальных данных таблицы,
а физическое расположение информации в данном индексе логически упорядочено.
В случае некластерных индексов
страницы уровня листа содержат не актуальные данные таблицы (как в случае
кластерного индекса), а указатель на строку данных, включающий номер
страницы данных и порядковый номер записи на станице. Некластерный индекс
не требует физического переупорядочения строк данных таблицы.
Двоичные
деревья являются динамически поддерживаемыми структурами, т.е при вставке, удалении или обновлении строк данных
информация в индексах также должна быть изменена для отражения выполненных в таблице изменений.
Для обработки страниц индексов требуются
дополнительные операции ввода-вывода.
Но при
разбивке страницы кластерного индекса не требуется вносить изменения в
информацию некластерных индексов, так как в SQL
Server 7 эти дополнительные операции ввода-вывода полностью исключены за счет
использования в некластерных индексах значений ключей
кластерного индекса вместо номеров физических страниц в случае, когда таблица
имеет оба типа индексов. При добавлении в кластерный индекс данные вставляются
в таблицу в правильной физической последовательности, соответствующей
логической упорядоченности индекса. Поэтому может потребоваться сместить
остальные строки таблицы вверх или вниз, в зависимости от места вставки данных.
Все это связано с выполнением дополнительных
операций ввода-вывода, необходимых для обработки данных индекса. Со
временем, по мере накопления данных на
странице, при вставке очередной записи
может потребоваться разбить информацию страницы на две части, так как
для новой записи уже не будет хватать свободного места. В результате часть
записей данных будет перенесена на новую страницу. В предыдущих версиях SQL
Server эта ситуация сопровождалась обновлением данных во всех некластерных индексах таблицы с целью отражения перемещения части строк на новую страницу.
Индексы таблиц хранятся в виде страниц. Каждая страница размером 8192 байт
включает заголовок, имеющий длину 96 байт. Еще один фрагмент страницы используется
для размещения других структур данных, например информации о переполнении
строк. Вся оставшаяся часть страницы (8060 байт) предназначена для размещения
данных. Каждая строка включает элемент индекса (значение индексируемого поля
таблицы) и идентификатор RowID (включающий идентификатор файла,
номер страницы, номер строки), указывающий на соответствующую запись в таблице.
20.3. Организация и оптимизация доступа к
данным
Вследствие объективно существующей разницы в скорости работы
процессоров и оперативной памяти с одной стороны, и устройств внешней памяти с
другой, буферизация страниц базы данных в оперативной памяти – единственно
реальный способ достижения удовлетворительной эффективности СУБД. Кроме этого
используется механизм распределенного хранения информации - расщепления
данных между файлами и файловыми
группам, физически размещаемыми на разных устройствах или RAID-массивах.
Логически такое устройство представляется как единое целое, но на самом деле
состоит из нескольких физических дисков. Данные на дисках размещаются блоками
одной длины и таким образом, легко могут быть распределены по всем дискам.
Стратегия буферизации, применяемая в операционных средах, не
соответствует целям и задачам СУБД, поэтому для оптимизации обработки данных
одной из главных задач СУБД является создание эффективной системы управления
процессом буферизации.
Память, управляемая СУБД, состоит из нескольких типов
буферов:
- буфера страниц данных, с
которыми работает СУБД;
- буфера страниц журнала
транзакций, которые отражают процесс выполнения транзакции – последовательности
операций над БД, переводящей БД из одного непротиворечивого состояния в другое
непротиворечивое состояние;
- системные буферы, которые
содержат общую информацию о БД, о пользователях, о физической структуре БД, о
базе метаданных.
Если бы запись об изменении базы данных реально немедленно
записывалась во внешнюю память, это привело бы к существенному замедлению
работы системы. Поэтому записи в журнал тоже буферизуются: при нормальной
работе очередная страница выталкивается во внешнюю память журнала только при
полном наполнении записями.
Но поскольку имеются два вида буферов, содержащих
взаимосвязанную информацию – буфер журнала и буфер страниц оперативной памяти,
которые могут выталкиваться во внешнюю память, буферы выделяются не для каждого
пользовательского процесса, а для всех процессов сервера. Это позволяет
увеличить степень параллелизма при исполнении клиентских процессов.
20.4. Физическая структура данных в СУБД Oracle
Единицами распределения
пространства базы данных являются блоки данных, экстенты и сегменты.
При создании объекта, такого как таблица или индекс,
создается сегмент этого объекта. Место для сегмента данных распределяется в
одном или нескольких файлах данных, составляющих табличное пространство (слайд
15).
Сегмент объекта может размещаться лишь в одном
табличном пространстве базы данных. Экстенты одного сегмента распределяются блоками
данных, возможно в нескольких файлах табличного пространства: таким
образом, объект может "занимать" один или несколько файлов данных. Но
при этом, отдельный экстент не может находиться в нескольких файлах (слайд
16).
Общая емкость памяти табличного
пространства определяется суммой размеров файлов данных, составляющих это
табличное пространство. Суммарная емкость всех табличных пространств базы
данных составляет общую емкость базы данных.
20.4.1. Сегменты
Сегмент - это совокупность
экстентов, распределенных для специфического типа данных, и находящихся в одном
и том же табличном пространстве. База данных ORACLE может содержать четыре
различных типа сегментов: сегмент данных, сегмент индекса, сегмент отката,
временный сегмент
Каждый тип сегмента состоит из
одного или нескольких экстентов. Когда существующее пространство в сегменте
полностью использовано, ORACLE распределяет для сегмента новый экстент.
Поскольку экстенты распределяются при необходимости, они не обязательно будут
смежными на диске, и могут быть распределены между различными файлами.
Отдельный экстент, однако, не может размещаться в нескольких файлах.
Каждый сегмент в базе данных
содержит заголовок, который описывает характеристики этого сегмента и
оглавление (список) экстентов в этом сегменте.
Сегменты данных. Каждая некластеризованная таблица
или кластер в БД ORACLE имеет единственный сегмент данных, содержащий все
данные этого объекта.
Сегменты индекса. Каждый индекс в базе данных ORACLE имеет единственный
сегмент индекса, содержащий все данные этого индекса.
Сегмент данных таблицы и сегмент
индекса не обязаны размещаться в одном и том же табличном пространстве.
Сегменты отката. Каждая база данных содержит один или несколько сегментов отката.
Сегмент отката - это часть базы данных, в которой записываются действия
транзакций, которые, возможно, придется отменить.
Временные сегменты. При обработке запросов ORACLE часто требует временного
рабочего пространства для промежуточных этапов обработки предложения SQL. Это
дисковое пространство, называемое ВРЕМЕННЫМ СЕГМЕНТОМ, распределяется
автоматически.
20.4.2. Экстенты
Экстент - это смежные блоки данных,
выделенные для хранения специфического типа информации. При создании объекта,
такого как таблица или индекс, создается сегмент этого объекта в
предназначенном табличном пространстве.
При распределении нового экстента
ORACLE отыскивает в табличном пространстве, содержащем сегмент, первый
свободный непрерывный участок блоков данных, размер которого больше
запрашиваемого размера, по крайней мере, на один блок. Если запрашиваемый участок
непрерывных блоков не найден, ORACLE соединяет все свободные блоки данных в
соответствующем табличном пространстве, так что формируются группы непрерывных
блоков большего размера. (Фоновый процесс SMON периодически объединяет смежное свободное пространство.)
20.4.3. Блоки данных
Данные БД хранятся в блоках
данных, называемых также логическими блоками, блоками ORACLE или
страницами. Один блок данных занимает фиксированное
размер (байт) физического пространства на диске, который устанавливается для
каждой базы данных при ее создании. Этот размер кратен размеру блока
операционной системы, но не превышает определенный максимум. Блок данных - это
наименьшая единица ввода-вывода СУБД.
Формат блока данных, независимо от
того, содержит ли он данные таблицы, индекса или кластера, включает: Общий и
переменный заголовок, Оглавление таблиц, Оглавление строк, Свободное
пространство, Строки данных.
Заголовок содержит общую информацию блока, такую как адрес блока и
тип сегмента. В среднем, суммарный размер фиксированной и переменной частей
блока составляют от 84 до 107 байт.
Оглавление таблиц содержит информацию о том, строки каких таблиц размещены в
этом блоке.
Оглавление строк содержит информацию о действительных строках в блоке (включая
адреса каждой порции строки в области данных строк). После того, как в оглавлении
строк распределено пространство, это пространство не освобождается при удалении
строки. Поэтому блок, который когда-то содержал до 50 строк, по-прежнему имеет
100 байт в заголовке для оглавления строк. Это пространство будет использовано
повторно лишь тогда, когда в блок вставляются новые строки.
Строки данных содержат данные таблицы или индекса. Строки могут переходить из блока
в блок, если все данные строки не умещаются в один блок. В таком случае данные
этой строки сохраняются в виде цепочки блоков данных, резервируемых в
этом сегменте. Если строка в блоке данных обновляется так,
что общая длина строки увеличивается, а свободное пространство в блоке
заполнено, то данные всей строки мигрируют, т.е. переносятся в, при условии,
что в новом блоке поместится вся строка. На месте мигрировавшей строки записывается
указатель на новый блок, содержащий мигрировавшую строку; ROWID мигрировавшей
строки не изменяется.
Свободное пространство в блоке используется для вставки новых строк и для обновлений
строк, требующих дополнительного пространства (например, при замене пустых хвостовых
значений на непустые значения). Будут ли конкретные вставки действительно осуществляться
в данном блоке - зависит от значения параметра управления пространством и от
текущей величины свободного пространства в блоке.
20.4.4. Типы индексов (слайд 17)
- Индексы на основе В*-дерева. Аналогичные по конструкции двоичному дереву,
они обеспечивают быстрый доступ по ключу к отдельной строке или диапазону
строк, требуя обычно очень немного чтений для поиска соответствующей строки.
Индекс на основе В*дерева имеет несколько подтипов:
- Таблицы, организованные по индексу.
Это таблицы, хранящиеся в структуре В*-дерева
- Индексы кластера на основе В*-дерева. Используются не для
перехода от ключа к строке, а для перехода от ключа кластера к блоку,
содержащему строки, связанные с этим ключом.
- Индексы с обращенным ключом. Это
индексы на основе В*-дерева,
байты ключа в которых инвертированы. Это используется для более равномерного
распределения записей по индексу при вводе возрастающих значений ключей.
Предположим, при использовании последовательности для генерации первичного
ключа генерируются значения 987500, 987501, 987502 и т.д. Поскольку это
последовательные значения, они будут попадать в один и тот же блок индекса,
конкурируя за него. В индексе с обращенным ключом сервер Oracle
будет индексировать значения 205789, 105789, 005789. Эти значения обычно будут
далеко отстоять друг от друга в индексе, и вставки в индекс будут распределены
по нескольким блокам.
-
Индексы
по убыванию. Индексы по убыванию позволяют отсортировать данные в структуре
индекса от "больших" к "меньшим",
а не от меньших к большим (по возрастанию).
-
Индексы
на основе битовых карт. Обычно в В*-дереве
имеется однозначное соответствие между записью индекса и строкой – запись
индекса указывает на строку. В индексе на основе битовых карт запись использует
битовую карту для ссылки на большое количество строк одновременно.
-
Индексы
по функции. Эти индексы на основе В*-дерева
или битовых карт хранят вычисленный результат применения функции к элементам
строки, а не сами данные строки.
-
Прикладные
индексы - индексы, которые строит и хранит приложение.
-
Текстовые
индексы interMedia - встроенные прикладные индексы
для обеспечения поиска ключевых слов в текстах большого объема.
20.4.5. Кластеры
КЛАСТЕРЫ - это необязательный
способ хранения данных таблиц. Кластер представляет собой группу таблиц,
разделяющих одни и те же блоки данных, потому что они имеют общие столбцы и
часто используются вместе.
Так как кластеры хранят связанные
строки разных таблиц вместе в одних и тех же блоках данных, при правильном
использовании кластеров достигаются два главных преимущества:
- Сокращается дисковый ввод-вывод и
улучшается время доступа для соединений по кластеризованным
таблицам.
- В кластере значение ключа
кластера представляет собой совокупность значений столбцов ключа кластера
для конкретной строки. Каждое значение ключа кластера хранится лишь один раз как в кластере, так и в индексе кластера, независимо от
того, сколько строк в различных таблицах содержат это значение. Поэтому для
хранения данных и индекса связанных таблиц требуется меньше места, чем для формата
некластеризованных таблиц.
