Внутренняя модель данных

Хранение базы данных
Логическая структура данных:
Таблица (двумерный или многомерный массив данных)
Древовидные иерархические структуры
Сетевые структуры
Структура в оперативной памяти:
Адресация по месту (логический или физический указатель)
Адресация по содержимому (по ключу)
Адресная функция:
- отображает логическую структуру данных на физическую структуру хранения

Таблица как список записей
Списковая структура:
X = ( X[1], X[2], X[3], … , X[n] )
X [ i ] – i-ый элемент линейного списка (запись/кортеж таблицы)
Типы записей:
Фиксированной длины
Переменной длины
Неопределенной длины

Записи фиксированной длины
S (структура) записи = const
M (размер) записи = const
Mi поля = const
(+) хорошая скорость обработки
(-) большой расход памяти
a1 | a2 | ...... | an | b1 | ...... | bn | ......
Запись 1
Запись 2

Записи переменной длины
S (структура) записи = const
M (размер) записи = var
Mi поля = var
Разделитель полей (рп)
Разделитель записей (рз)
a1 | рп | a2 | рп | ...... | an | рп | рз | ........
Запись 1
Запись 2

Записи неопределенной длины
S (структура) записи = var
M (размер) записи = var
Mi поля = var
Разделитель полей (рп)
Разделитель записей (рз)
A7 | рп | a7 | рп | А4 | рп | a4 | рп | рз | ……
Запись 1
Запись 2
Ai (имя) | ai (значение)
NULL | NULL | NULL | a4 | NULL | NULL | a7
A1 A2 A3 A4 A5 A6 A7

Хранение списковых структур в оперативной памяти
Реализация адресной функции:
Последовательное распределение памяти
Связанное распределение памяти
a | v | f | g | k | l | h | k | c | d | h | m | r | s | ………..
Оперативная память как последовательность байт:

Последовательное распределение памяти
Последовательный список:
Уi – элемент списка
N – количество элементов массива
m – размер элемента списка
B – адрес начала списка (база)
Адресная функция:
a(i) = B + (i-1)*m
Позволяет хранить древовидные структуры

Последовательный список для регулярного двоичного дерева
Адресная функция
a(k) = B+(k-1)*m

Связанное распределение памяти
Связанный список
Цепная структура/Цепь
Особенности:
Элементы хранят в любом месте ОП
Последовательность элементов задают указатели
В инвентарных таблицах БД хранят указатель на начало списка (голову)
Л – конец списка (спец. символ)
X [3] | *
X [5] | л
X [2] | *
X [1] | *
X [4] | *
Вход

Использование связаных списков
(+) гибкость, изменение структуры без переноса данных
(-) больший объем хранения
X [3] | *
X [5] | л
X [2] | *
X [1] | *
X [4] | *
Вход
X [3] | *
X [5] | л
X [1] | *
X [4] | *
Вход

Виды списков
Список (цепь/цепная структура) с одним указателем
Цепь с двумя указателями (Список с обратным проходом)
Хранят указатель на голову и на хвост
Обход в прямом направлении и обход в обратном направлении
x1 | *
Вход
x5 | л
x4 | *
x3 | *
x2 | *
Вход
x1 |л|*
Вход
x5 |*|л
x4 |*|*
x3 |*|*
x2 |*|*

Список с пропусками
Цепь с пропусками (Мультицепь)
Указатель на группу в прямом или обратном направлении
Оптимальный размер группы r(n) при количестве элементов n
a1 |*|*
Вход
b3 |*|-
b2 |*|-
b1 |*|*
a2 |*|-
c1 |л|л

Кольцевые списки (кольца)
Однонаправленный циклический список
(+) Каждый элемент достижим из каждого

Двунаправленный циклический список

Коралловое кольцо
Каждый элемент имеет указатель на голову списка

Кольца с пропусками
a1 |*|*
Вход
b3 |*|-
b2 |*|-
b1 |*|*
a2 |*|-
c1 |*|*

Многосвязанные списки
Виды линейных списков
Однонаправленные
Двунаправленные
циклические
Используются для организации древовидных и сетевых структур

Типы указателей
Абсолютный
физический адрес памяти
(+) скорость
(-) жесткая привязка
Относительный
базовый адрес
расстояние между элементами списка
Символический
адрес вычисляется по значению ключа
если совпадает, то цепочка
(+) независимость изменения элемента
(-) низкая скорость

Виды указателей
По организации структуры данных:
Встроенные (часть записи)
Справочник (хранятся отдельно)
Назначение:
Направление доступа
Цепочки связных данных
Семантические связи данных

Методы представления древовидных структур
Допустим, что данные узла – это записи фиксированной длины
1-й уровень
2-й уровень
3-й уровень
4-й уровень

Метод указателей на порожденные записи
(+) обход БД в прямом направлении
(-) Переменное количество указателей

Метод указателей на исходные записи
(+) минимум указателей
(-) много точек входа

Метод указателей на порожденные и исходные записи
Сочетает указатели на исходные и указатели на порожденные
На первом месте ставят указатель на исходную запись
Храниться только указатель на корень дерева
(+) большая надежность
(+) прямой и обратный обход
Xi | * | * | * | *
Указатели на порожденные записи
Указатель на исходную запись

Метод указателей на порожденные и подобные записи
с кольцевыми структурами
(+) В прямом и обратном направлении
(+) Постоянное количество указателей (2)

Метод справочника
Файл данных (записей)
Файл справочника
Файл индекса

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

Пример сетевой структуры