Физическая организация данных в БД. Словари баз данных.

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

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

Последовательный метод доступа

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

Существуют два класса методов, реализующих доступ к данным по ключу:

• методы поиска по дереву,
• методы хеширования.

Индексно-последовательный метод доступа

Бинарное дерево

1. R-дерево

Определение: Деревом называется конечное множество, состоящее из одного или более элементов, называемых узлами, таких, что:

1. между узлами имеет место отношение типа "исходный-порожденный";
2. есть только один узел, не имеющий исходного. Он называется корнем;
3. все узлы за исключением корня имеют только один исходный; каждый узел может иметь несколько порожденных;
4. отношение "исходный-порожденный" действует только в одном направлении, т.е. ни один потомок некоторого узла не может стать для него предком.

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

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

Упорядоченное дерево, степень которого не больше 2 называется бинарным деревом. Бинарное дерево особенно часто используется при поиске в оперативной памяти. Алгоритм поиска: вначале аргумент поиска сравнивается с ключом, находящимся в корне. Если аргумент совпадает с ключом, поиск закончен, если же не совпадает, то в случае, когда аргумент оказвается меньше ключа, поиск продолжается в левом поддереве, а в случае когда больше ключа - в правом поддереве. Увеличив уровень на 1 повторяют сравнение, считая текущий узел корнем.

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

Определение: Бинарное дерево называют сбалансированным (balanced), если высота левого поддерева каждого узла отличается от высоты правого поддерева не более чем на 1.

В-дерево и В+-дерево

Занесение новой записи

Удаление записи

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

Определение: В-деревом порядка n называется сильно ветвящееся дерево степени 2n+1, обладающее следующими свойствами:

1. Каждый узел, за исключением корня, содержит не менее n и не более 2n ключей.
2. Корень содержит не менее одного и не более 2n ключей.
3. Все листья расположены на одном уровне.
4. Каждый нелистовой узел содержит два списка: упорядоченный по возрастанию значений список ключей и соответсвующий ему список указателей (для листовых узлов список указателей отсутствует).

Для такого дерева:

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

Включение в B-дерево

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

1. В вершине-листе есть место для нового ключевого значения. В этом случае ключ вставляется в соответствующее место этой вершины.

2. Вершина-лист уже содержит 2n ключей. В этом случае выполняются следующие действия. Новый ключ вставляется в соответствующее место данной вершины. После этого вершина будет иметь 2n+1 ключей, что недопустимо.

Поэтому эту вершину необходимо разделить на две вершины, содержащие n ключей каждая, причем в левую вершину попадут ключи k1, ..., kn, а в правую – kn+2, ..., k2n+1. Ключ kn+1, т.е. средний ключ последовательности, должен быть включен в вершину-предок для данной вершины. Если в вершине-предке было меньше 2n ключей, то процесс

заканчивается.

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

Описанная процедура вставки сохраняет все свойства B-деревьев.

Рассмотрим операцию включения на примере создания B-дерева степени

2 при следовании ключей в следующем порядке (20, 40, 10, 30, 15; 35, 7, 26, 18,

922; 5; 42, 13, 46, 27, 8, 32; 38, 24, 45, 25;). В этом случае результирующее дерево

имеет вид (*) .

Исключение элемента из B-дерева

При исключении элемента из B-дерева возможны два варианта.

1. Исключаемый элемент находится на листовой странице. В этом случае алгоритм удаления достаточно прост.

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

В любом случае, после уменьшения размера страницы необходимо проверить количество элементов, оставшихся на этой странице. Если это количество стало меньше n, то нарушится одно из свойств B-дерева. В этом случае необходимо выполнить некоторые дополнительные действия. Один из возможный вариантов решения этой проблемы –

позаимствовать элементы с одной из соседних страниц, назовем ее Q. В этом случае элементы исходной страницы Т и страницы Q поровну распределяются на обе страницы. Этот процесс называется балансировкой страниц. Однако может случиться так, что в странице Q нечего занимать, т.к. ее размер уже равен минимальному – n. В этом случае общее число элементов на страницах Т и Q равно 2n-1, и мы можем слить две страницы в одну, добавив сюда средний элемент из родительской для Т и Q страницы, а затем уничтожить страницу Q. Эти действия в точности обратны процессу разделения страниц при добавлении новых элементов.

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

Пусть дано B-дерево второй степени (*). Рассмотрим процесс удаления

элементов из этого дерева в следующем порядке: 25, 45, 24; 38, 32; 8, 27, 46, 13,

42; 5, 22, 18, 26; 7, 35, 15;. В результате должно получиться следующее B-

дерево.

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

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

R-дерево (R-Tree)

это индексная структура для доступа к пространственным данным, предложенная А.Гуттманом (Калифорнийский университет, Беркли). R-дерево допускает произвольное выполнение операций добавления, удаления и поиска данных без периодической переиндексации.

Оно подобно B-дереву, но используется для организации доступа к пространственным данным, то есть для индексации многомерной информации, такой, например, какгеографические

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

Для представления данных используются записи, каждая из которых имеет уникальный идентификатор (tuple-identifier). В каждом концевом узле (листе) дерева содержится запись вида(I,tuple-identifier), где I - n-мерный параллелепипед, содержащий указатели на пространственные данные (его также называют minimal bounding rectangle, MBR), а каждый элемент в tuple-identifier содержит верхнюю и нижнюю границу параллелепипеда в соответствующем измерении.

Неконцевые узлы содержат записи вида (I, childnode-pointer), где I минимальный ограничивающий параллелепипед для MBR всех узлов, производных по отношению к данному.Childnode-pointer - это указатель на производные узлы.

Пусть M и m <= M/2 соответственно максимальное и минимальное количество элементов, которое может быть размещено в узле. Тогда свойства R-дерева можно описать следующим образом: