Внутренняя организация реляционных СУБД

🕛 22.05.2009, 11:48

Особенности данных СУБД:
- 2 уровня представления - уровень, на котором производится непосредственное управление данными во внешней памяти (единицами являются физические сектора, кластеры, буферы или цепочки буферов ОЗУ) и языковой уровень - язык SQL (единица отношения, кортежи, атрибуты);
- наличие специальных отношений - каталогов, которые содержат информацию об именовании объектов, пути доступа к объекту и конкретные средства этих объектов (владелец, ключ индекса и т.д.);
- регулярность структур данных;
- необходимо поддерживать избыточность данных: резервные копии для поддержания безопасности работы (журнальные структуры) и восстановлении при сбоях.
В СУБД можно выделить несколько структур (объектов во внешней памяти):
- стоки отношений - основная часть БД, видимая пользователю;
- управляющие структуры - индексы:
1) по инициативе пользователя;
2) по инициативе верхнего уровня для быстрого доступа;
3) по инициативе системы нижнего уровня для размещения данных и автоматической поддержки индексов при изменении данных(!);
- журнальная информация, фиксирующая все изменения в БД;
- служебная информация для обеспечения работы нижнего уровня (о свободном дисковом пространстве).
1 Хранение отношений
существует 2 подхода к физической организации хранения:
1. кортежное хранение(!) - более распространённое;
2. поатрибутное хранение.
При 1 обеспечивается быстрый доступ к целому кортежу, но т.к. в разных кортежах значения атрибутов могут дублироваться, то такая БД может создать лишнюю дублируемую информацию, и если требуется часть кортежа, то может потребоваться лишнее обращение к памяти. При 2 столбец хранится с исключёнными дубликатами  требуется меньше внешней памяти; при операциях соединения есть преимущества; но требуются дополнительные операции, когда требуется целый кортеж.
В основе 1 лежит страничная организация внешней памяти. Страница внешней памяти = страница кадра ОЗУ.

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

Как правило, с одной страницей связывается одно отношение. Если хранить на одной странице несколько отношений, то это усложнит структуру описателей. Встаёт проблема реорганизации при добавлении столбцов: новое отношение вводится только для новых кортежей, а в старых могут быть неопределённые значения. При удалении какого-либо отношения (?).
При 2 гранится полный набор доменов, но для доступа необходим целый кортеж, а следовательно его нужно «сконструировать», т.е. должна быть информация, описывающая для каждого кортежа - кортеж такой же степени, содержащий ссылки на места расположения необходимой информации в соответствующих столбцах: <{домен, №_элемента_в_домене}>.
Память используется экономно, но манипуляции с такими данными требуют более сложных и длительных операций (поиск и т.п.), но простые реляционные операции (ограничение, объединение и т.п.) более легки в выполнении.
2 Индексы
главное назначение - обеспечить эффективный прямой доступ к кортежу по ключу. Обычно определяется для одного отношения и строится по значению какого-либо атрибута. Если этот атрибут является ключом отношения, то индекс должен быть уникальным, т.е. не содержать дублированных значений ключа.
Помимо таких индексов рассматриваются индексы, связанные с несколькими отношениями (мультииндексы). В них ключ индекса является составным, по отдельным составляющим его составляются кортежи из разных отношений. Такие мультииндексы используются для сложных операций (эквисоединение).
Общая идея организации - хранение упорядоченного списка ключей с привязкой к каждому ключу идентификатора кортежа или списка идентификаторов кортежа, если ключи индекса не уникальны.
Отношение А индекс отношения А по ключу Атр.1
Атр.1 | | ключ | tid |
a | | a | 1 | ключ | tid
b | |  a | 4 | или a | 1, 4 - список tid
c | | b | 2 | b | 2
a | | c | 3 | c | 3

Отношение B индекс отношения B по ключу Атр.2
Атр.2 | | ключ | tid |
10 | | 2 | 2 |
2 | |  8 | 4 |
14 | | 10 | 1 |
8 | | 14 | 3 |

мультииндекс отношений А и В по ключам Атр.1 и Атр.2:
| a 2 | 1, 2 || a 14
| a 2 | 4, 2 || a 14
| a 8 | ... || b 2
| a 8 | || b 8
| a 2 | || ...
| a 2 | ||
Большинство СУБД строит индекс сразу, как только определит ключ. Существует много способов построения индексов, но самым распространённым является способ «B(b)-деревьев».
B-дерево обладает двумя свойствами:
1) сбалансированность - длина пути от корня до любого места одна и та же;
2) ветвистость - это свойство каждого узла ссылаться на большое количество потомков.
Каждый узел B-дерева соответствует страница ВП. Внутренние страницы и листовые страницы должны иметь разную структуру:
I. внутренняя.
№1(ключ 1), №2(ключ 2), …, №m(ключ m): здесь содержатся номера страниц и ключи.
Ключ каждой страницы удовлетворяет условиям:
- кл.1 <= кл.2 <= … <= кл.m (<= - предшествует или равен);
- на странице №S находятся ключи: кл.S <= k <= кл.(S+1).
II. листовая.

Кл.1 <= кл.2 <= …
А списки - списки идентификаторов кортежей, которые имеют отношение к данному ключу. Элементы в списке могут быть однонаправленными или двунаправленными:

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

Скорость операции сравнения: (поиск) logmn,
Где n - число ключей, m - степень ветвистости.
Основная проблема - поддержание свойств B-дерева при добавлении и исключений записей.
Рассмотрим алгоритм добавления новой записи:
1) поиск по ключу: если B-дерево не содержит записей с таким ключом, то будет получен № страницы, где этот ключ должен содержаться;
2) вставка: нужно вытащить эту страницу в буфер ОЗУ и там модифицировать листовую страницу:
- если размер достаточен, то вытолкнуть после модификации во ВП;
- если информации на странице больше, чем её размер (переполнение буфера), необходимо её расщепить. Т.е. эта страница делится на две, каждая из которых меньше объёма буфера, но на новую страницу необходимо добавить ссылку, а, следовательно, на предыдущей уровень нужно внести изменения в список ключей. Если эта страниц тоже переполнилась, то её опять нужно расщепить и т.д. Если вдруг переполнится корневая страница, то придётся её расщепить, а создать новый корень над ними.
При удалении записей алгоритм обладает теми же особенностями:
поиск: если запись не найдена, то и удалять нечего, иначе физическое удаление соответствующего ключа и после этого проверка: если информации на странице очень мало, то можно осуществить слияние этой страницы с «левым» или «правым» соседом и после этого откорректировать список предыдущего уровня.
Для большей эффективности используется упреждающее расщепление не при переполнении, а по достижении заполненности страницы некоторого уровня.
В литературе такие деревья называют B+, B*. Альтернативой B-деревьев является хеширование информации.
3 Хеширование
общая идея - «перемешать» записи с различными ключами, т.е. сопоставление каждому ключу уникального значения, определяющего место хранения.
Функция перевода по ключу - хэш-функция. Ключ -> А хранения
Ключи 1  1000 1 -> 0001 600 -> 0600 1000 -> 1000
при таком хранении ключей требуется много памяти:
ключи: 20, 20, 444, 981; память: 20  981
Поэтому, как правило ХЭШ (свёртка) выдаёт значение, когда нескольким ключам соответствует один А хранения. Тогда вычисляется: А = hash (ключ). По этому А проверяется наличие какой-либо цифры, если она есть, то организуется список (ключей) информации, если нет, то сохраняется исходное значение.

4 Журнальная информация
В журнале должны хранится все изменения, происходящие в БД. С технической точки зрения журнал должен представлять файл последовательного доступа с записями переменного размера. Конкретная структура записей является частным делом каждой реализации. Журнал недоступен пользователю, а доступен самой СУБД. Из соображения надёжности существует несколько копий журнала на разных носителях.
5 Служебная информация
Служебная информация необходима для корректной работы с внешней памятью. В число файлов служебной информации входят:
- внутренние каталоги, которые описывают свойства объектов БД;
- описатели свободной и занятой памяти в терминах страницы;
- информация, которая связывает страницы одного отношения (если в одном файле внешней памяти располагается несколько отношений, то страницы каждого отношения должны быть связаны между собой).
Самый простой способ связывания - прямые ссылки. Но они неудобны тем, что затрудняют совместную обработку страниц при многопользовательской работе. Поэтому стараются использовать косвенное связывание с помощью каких-нибудь служебных индексов.