1.1.2. Обобщенные структуры или модели данных.

Мы рассмотрели несколько типов структур, являющихся совокупностями элементов данных: массив, дерево, запись. Более сложный тип данных может включать эти структуры в качестве элементов. Элементами записи может быть массив, стек, дерево. Обобщенные структуры называют моделями данных, поскольку они отражают представление пользователя о данных реального мира. Любая модель данных должна содержать три компоненты:

1. структура данных - описывает точку зрения пользователя на представление данных.

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

3. ограничения целостности - механизм поддержания соответствия данных предметной области на основе формально описанных правил.

В процессе исторического развития в СУБД использовалось следующие модели данных:

• иерархическая,

• сетевая,

• реляционная.

В последнее время все большее значение приобретает объектно-ориентированный подход к представлению данных.

1.2. Методы доступа к данным.

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

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

• методы поиска по дереву,

• методы хеширования.

1.2.1.Методы поиска по дереву.

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

1. между узлами имеет место отношение типа "исходный-порожденный";

2. есть только один узел, не имеющий исходного. Он называется корнем;

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

4. отношение "исходный-порожденный" действует только в одном направлении, т.е. ни один потомок некоторого узла не может стать для него предком.

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

Используется следующее правило сравнения строковых переменных: считается, что значение символа соответствует его порядковому номеру в алфавите. Поэтому "И" меньше "К", а "К" меньше "С". Если текущие символы в сравниваемых строках совпадают, то сравниваются символы в следующих позициях.

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

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

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

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

1. Каждый узел, за исключением корня, содержит не менее n и не более 2n ключей.

2. Корень содержит не менее одного и не более 2n ключей.

3. Все листья расположены на одном уровне.

4. Каждый нелистовой узел содержит два списка: упорядоченный по возрастанию значений список ключей и соответствующий ему список указателей (для листовых узлов список указателей отсутствует).

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

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

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

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

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

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

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

• R-дерево является сильно сбалансированным деревом, т.е. все листья находятся на одном уровне.

• Корневой узел имеет, как минимум, двух потомков.

• Для каждого элемента (I,childnode-pointer) в неконцевом узле I является наименьшим возможным параллелепипедом, т.е. содержит все параллелепипеды производных узлов.

• Каждый концевой узел (лист) содержит от m до M индексных записей.

• Для каждой индексной записи (I,tuple-identifier) в концевом узле I является параллелепипедом, который содержит n-мерный объект данных, на который указывает tuple-identifier