Тема_11_Физические структуры данных

1.

Тема 11
Физические структуры данных

2.

Внутренняя схема БД
Состав внутренней схемы базы данных
Данных
Прикладная и
интерфейсная части
Индексов
Страницы
структура БД;
ограничения
целостности
данных.
Информационные
массивы
Страницы
Системная
информация по
БД (каталог БД)
запросы;
процедуры;
события;
правила;
код интерфейса.
Единый файл или совокупность файлов

3.

Внутренняя схема БД
Состав внутренней схемы базы данных
1. Информационные массивы, включающие:
• данные;
• массивы индексов, являющихся специальными дополнительными
конструкциями для ускорения доступа к данным основных
информационных объектов.
2. Каталог БД, в котором размещается системная информация по
логической структуре БД, включающая:
• описание основных информационных объектов (имена,
структура, параметры, связи);
• ограничения целостности данных.
3. Прикладной
компонент,
образуемый
совокупностью
интерфейсных элементов представления, ввода и обработки
данных, типовых запросов и процедур обработки данных, а также
«событий» и «правил», отражающих правила и специфику
предметной области АИС.
Все три части внутренней структуры и их составные элементы (например, информационные
массивы отдельных информационных объектов БД) могут размещаться в одном едином файле базы
данных или в разных файлах. Во втором случае внутренняя схема БД определяется совокупностью
и порядком расположения данных файлов.

4.

Внутренняя схема БД
Общий принцип организации
внутренней схемы базы данных
ОПЕРАТИВНАЯ
ПАМЯТЬ (ОЗУ)
Обмен
страницами
Буферы страниц
Страница 1
Запись 1
Запись 2
Запись 3
.....
Страница 2
Запись 1
Запись 2
Запись 3
.....
.....
УСТРОЙСТВО ДИСКОВОЙ
(ВНЕШНЕЙ) ПАМЯТИ
Файл(ы) данных и индексов
Считывание
страниц
с нужными
записями
Выталкивание
и фиксация
страниц
Данные
Страница 1
Запись 1
Запись 2
Индексы
Страница 1
.....
Страница 2
Запись 1
Запись 2
.....
.....
Страница 2
.....

5.

Физические структуры данных
-способы организации записей в страницах (расположение, добавление,
корректировка, удаление), которые образуют третий (низший) уровень
представления информации в информационной системе.
Уровни представления данных:
Прикладная
область
Данные
Концептуальный уровень
Пользователь,
Разработчик
информационной
системы
Прикладной
программист
Логический (внешний) уровень
БД
Физический (внутренний) уровень
СУБД

6.

Физические структуры данных:
- линейные – в одну страницу файла БД объединяются записи-кортежи
одной таблицы (информационного объекта), которые располагаются в
последовательном (линейном) порядке друг за другом, каких-либо
ссылок и указателей на связи между записями не предусматривается;
- нелинейные
–
записи
одного
информационного
объекта
необязательно располагаются друг за другом на одной странице файла
данных, но обязательно содержат специальные указатели на
следующую запись объекта (односвязные списки) или на связанные
записи других информационных объектов (многосвязные списки,
древовидные структуры).

7.

Линейные структуры
При добавлении записи каждая новая запись помещается
непосредственно за последней. Если страница заполняется, то для
соответствующей таблицы выделяется дополнительная страница.
Дисковое пространство
Ячейки памяти
1-я
запись
2-я
запись
…
1-я страница
n+1
запись
n+2
запись
n-я
запись
2-я страница

8.

Линейные структуры
Удаление записей может производиться 2 способами:
1) сразу же осуществляется автоматическое перезаписывание на новых
позициях всех строк – записей, лежащих за удаляемыми.
Достоинство – максимальная эффективность использования дискового
пространства.
Недостаток – существенные затраты при любых операциях по удалению
записей
1-я
запись
2-я
запись
…
i-1
запись
i
запись
i+1
запись
i+2
запись
…
i
зап

9.

Линейные структуры
2) простое «вычеркивание» удаляемой записи без перезаписывания,
появление пустых мест в страницах файла данных
Достоинство – высокая производительность.
Недостаток - неэффективное использование дискового пространства
(устраняется путем автоматической/ручной дефрагментацией БД)
1-я
запись
2-я
запись
…
i-1
запись
i
запись
i+1
запись
i+2
запись
i+3
запис

10.

Линейные структуры
Линейная структура текстового файла
Дисковое пространство
Информационная часть
1 строка
Заголовок
2 строка
3 строка
1 страница
4 строка
5
...
строка
2 страница
Последовательность строк-записей с разделителем «
(строки имеют различную длину)
»
Достоинство – максимальная эффективность использования дискового
пространства.
Недостатки - нет возможности быстрого прямого доступа к нужной строке,
так как местоположения записей постоянно меняются, значительные
временные затраты на перезаписывание записей

11.

Линейные структуры
Линейная структура dbf-файла
Дисковое пространство
Информационная часть
Заголовок
Блок описания
1-я запись 2-я запись 3-я запись 4-я запись ...
структуры
1-я страница
2-я страница
...
Последовательность байтов записей без
разделителей
Достоинство – обеспечивается прямой доступ к любой записи.
Недостаток – невысокая эффективность использования
пространства
дискового

12.

Нелинейные структуры
Односвязные списки
Адреса ячеек памяти
ai
aj
i-я запись
aj
an
j-я запись
ak
ai
k-я запись
Достоинство – обеспечивается более эффективный, чем в линейных
структурах, доступ к данным.
Недостаток – существенно большие и сложные по сравнению с линейными
структурами затраты и процедуры преобразования (перетряски) файла базы
данных при любых операциях добавления, удаления и корректировки
записей

13.

Нелинейные структуры
Нелинейная древовидная иерархическая структура
Записи одной
страницы
1-я 2-я 3-я
Дисковое пространство
...
Страница
записей на
стороне «один»
корень
1-я 2-я 3-я
...
Страница
подчиненных
записей (на
стороне
«многие») для
первой записи
из страницы на
стороне «один»
1-я 2-я 3-я
...
Страница
подчиненных
записей (на
стороне
«многие») для
второй записи
из страницы на
стороне «один»
1-я подчиненная 2-я подчиненная
внутренняя
внутренняя
вершина
вершина
1-я 2-я
...
1-я
...
Страница
подчиненных
записей (на
стороне
«многие») для
третьей записи
из страницы на
стороне «один»
3-я подчин.
внутренняя
вершина
Лист

14.

Обеспечение эффективного доступа к данным
Индексирование данных
Индексные массивы:
-линейные;
-нелинейные.
Пример инвертированного списка
Значение индексируемого
поля («Год рождения»)
Номера строк
1958
3
1959
5, 17, 123, 256
1960
31, 32, 77
1962
11, 45, 58, 167, 231
1963
7, 8, 9, 10, 234, 235, 236

15.

Обеспечение эффективного доступа к данным
Расстановка (хеширование) записей
Номера
(адреса)
записей
Выделенная под данные область памяти
1
2
ni
3
...
i-я новая запись
значение ее ключевого поля
...
добавление новой записи по
соответствующему адресу
Клi
h(Клi)=ni
хеш-свертка
j-я старая запись
значение ее ключевого поля
nj
считывание
записи по соотв.
адресу
Клj
h(Клj)=nj

16.

Обеспечение эффективного доступа к данным
Расстановка (хеширование) записей
Требования к хеш-функциям:
1) ее результат для возможного диапазона значений ключевого поля
должен находиться в пределах диапазона адресов (номеров)
области памяти, выделяемой под данные,
2) значения функции в пределах выделенного диапазона адресов
должны быть равномерными.
На практике наиболее широкое распространение нашли хеш-функции, основанные на
операциях деления по модулю:
где (Кл. mod М) означает операцию деления по модулю М, а число М
выбирается исходя из необходимости попадания значений хеш-функции в
требуемый диапазон

17.

Обеспечение эффективного доступа к данным
Расстановка (хеширование) записей
Коллизии – ситуации появления одинаковых значений хешсверток при разных значениях полей (так называемые синонимы)
Подходы к разрешению коллизий
1. Использование технологии цепных списков - присоединение к
записям, по которым возникают коллизии, специальных
дополнительных указателей, по которым размещаются новые
записи, конфликтующие по месту расположения с ранее
введенными.
2. Использование дополнительного преобразования ключей
где ni(0)- исходное конфликтующее значение адреса записи;
g(Клi)- дополнительное преобразование ключа;
ni(доп)- дополнительное значение адреса.
где f(k) - некоторая функция над
номером итерации (пробы)