Физические модели баз данных

Сентябрь 2, 2022

Главная
Алгебра
Физические модели баз данных

Содержание

2. Внешние устройства хранения информации Устройства произвольного доступа (например, магнитные диски). Файлы с постоянной длиной записи. Местоположение
3. Физическая модель Далее будем рассматривать только файлы с постоянной длиной записи Упрощение: для каждой таблицы отдельный
4. Физическая модель Логическая запись (запись) – кортеж отношения Физическая запись (страница, блок) – единица обмена данными
5. Физическая модель На производительность СУБД влияют: Организация файла: распределение данных по записям и страницам на внешнем
6. Последовательная неупорядоченная организация файла Последовательный неупорядоченный файл (куча) – простейший тип структуры файла Записи размещаются в
7. Метод дихотомии На примере упорядоченного массива: Найти срединный элемент. Выбирается та половина на которая должна содержать
8. Последовательная упорядоченная организация файла В последовательных упорядоченных файлах записи упорядочены по одному или нескольким полям Поиск
9. Хеширование данных Основная идея – записи в файле прямого доступа находятся в «перемешанном» порядке (hash =
10. Хеширование данных Коллизия: h(Ki) = h(Kj) Значения таких ключей – «синонимы» Способы разрешения коллизий: Область переполнения:
11. Хеширование данных Несвязанная область переполнения Основная область Область переполнения (последовательное неупорядоченное хранение) Адрес = PK mod5
12. Хеширование данных Связанная область переполнения Область переполнения (связанный список) Основная область
13. Хеширование данных Свободное замещение Основная область вставка предыдущий следующий
14. Индексные файлы Снижение времени поиска: Бинарный поиск Часть индексного файла – в оперативной памяти
15. Файлы с плотным индексом Индексный файл Основная область Страница 1 Страница 2 Новая запись Новая индексная
16. Файлы с неплотным индексом Индексный файл Основная область Страница 1 Страница 2 Новая запись
17. Многоуровневые индексы Индексный файл 2 Основная область Индексный файл 1
18. Вторичные ключи Вторичный ключ – произвольный набор атрибутов, которому соответствует набор искомых записей в операции выборки
19. Вторичные ключи Значения вторичного ключа Номер страницы со списком адресов Значения вторичных ключей могут быть изменены,
20. Индексы в Transact-SQL Виды индексов: Кластерный (неплотный индекс). Один на таблицу. Для первичного ключа автоматически создается
21. Индексы в Transact-SQL Способы задания индексов: Автоматическое создание при объявлении первичного ключа. Объявление PRIMARY KEY создает
22. Индексы в Transact-SQL Сокращенное описание CREATE [ UNIQUE ] [ CLUSTERED | NONCLUSTERED ] INDEX index_name
24. Скачать презентацию

Слайд 2

Внешние устройства хранения информации
Устройства произвольного доступа (например, магнитные диски). Файлы с

постоянной длиной записи. Местоположение записи файла определяется адресом.
Устройства последовательного доступа (например, стример). Файлы с переменной длиной записи

A = BA + (k-1)*LZ + 1
A3= BA+(3-1)*20+1=BA+41

Слайд 3

Физическая модель
Далее будем рассматривать только файлы с постоянной длиной записи
Упрощение: для

каждой таблицы отдельный файл

Слайд 4

Физическая модель
Логическая запись (запись) – кортеж отношения
Физическая запись (страница, блок) –

единица обмена данными между первичной и внешней памятью

Порядок выполнения операции над данными (в общем случае):
1) Найти страницу на внешнем носителе, содержащую нужную запись
2) Прочитать страницу в первичную память
3) Найти нужную запись в прочитанной странице
4) Выполнить действие над записью в первичной памяти
5) Сохранить страницу с измененной записью во вторичной памяти

БД

страницы

Слайд 5

Физическая модель
На производительность СУБД влияют:
Организация файла: распределение данных по записям и

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

Слайд 6

Последовательная неупорядоченная организация файла
Последовательный неупорядоченный файл (куча) – простейший тип структуры

файла
Записи размещаются в файле в том порядке, в котором добавляются – новая запись на последнюю страницу
При удалении записи место повторно не используется, поэтому потеря эффективности со временем. Требуется периодическая реорганизация
Требуется периодически перестраивать файл
Поиск записи – линейный поиск, перебор всех страниц (чтение страницы, поиск внутри страницы)
Удаление записи – найти нужную страницу, загрузить, изменить страницу в памяти, сохранить на место
Такая организация эффективна при пакетной загрузке данных (последовательных)

Слайд 7

Метод дихотомии
На примере упорядоченного массива:
Найти срединный элемент. Выбирается та половина на

которая должна содержать заданное значение (по результатам сравнения значения со значениями левой и правой границ половин)
Если элемент не является границей, то в качестве исходного элемента рассматривается выбранная половина. Переход к п.1.
Среднее количество операций ~ln2(n), а последовательный поиск ~n

16?

итерации

Слайд 8

Последовательная упорядоченная организация файла
В последовательных упорядоченных файлах записи упорядочены по одному

или нескольким полям
Поиск выполняется быстро методом дихотомии (бинарный поиск)
Операция вставки – трудоемкая:
найти страницу для вставки
если на странице есть свободные места – перестроить записи на странице, если нет – то надо сдвинуть все записи к концу. Вставка в начало наиболее трудоемкая
Удаление – быстрая операция, т.е. после удаления файл не перестраивается

Модификация: область переполнения – последовательное неупорядоченное хранение

Слайд 9

Хеширование данных
Основная идея – записи в файле прямого доступа находятся в

«перемешанном» порядке (hash = путаница): записи с близкими значениями ключа находятся далеко друг от друга. Поэтому при вставки записи велика вероятность того, что соответствующее место будет свободно и перестраивать файл не потребуется
Функция перемешивания A = h(K), где K – значение ключа записи, A – адрес в файле. K – числовое поле, либо однозначно приводится к числовому виду.
Например, A = K mod N, где N – некоторое заранее заданное число, mod – операция получения остатка от деления по модулю N.

близкие значения ключей, дальние адреса

конфликты – одинаковые значения адресов

Слайд 10

Хеширование данных
Коллизия: h(Ki) = h(Kj)
Значения таких ключей – «синонимы»
Способы разрешения коллизий:
Область

переполнения:
несвязанная
связанная
Свободное замещение

Слайд 11

Хеширование данных
Несвязанная область переполнения
Основная область
Область переполнения (последовательное неупорядоченное хранение)
Адрес =
PK

mod5

Слайд 12

Хеширование данных
Связанная область переполнения
Область переполнения (связанный список)
Основная область

Слайд 13

Хеширование данных
Свободное замещение
Основная область
вставка
предыдущий
следующий

Слайд 14

Индексные файлы
Снижение времени поиска:
Бинарный поиск
Часть индексного файла – в оперативной памяти

Слайд 15

Файлы с плотным индексом
Индексный файл
Основная область
Страница 1
Страница 2
Новая запись
Новая индексная запись

Слайд 16

Файлы с неплотным индексом
Индексный файл
Основная область
Страница 1
Страница 2
Новая запись

Слайд 17

Многоуровневые индексы
Индексный файл 2
Основная область
Индексный файл 1

Слайд 18

Вторичные ключи
Вторичный ключ – произвольный набор атрибутов, которому соответствует набор искомых

записей в операции выборки (значения ключа – не уникальные)

Слайд 19

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

быть изменены, поэтому перестройка индекса требуется не только при INSERT и DELETE, но и при UPDATE

Слайд 20

Индексы в Transact-SQL
Виды индексов:
Кластерный (неплотный индекс). Один на таблицу. Для первичного

ключа автоматически создается кластерный индекс, если не указан тип NONCLUSTERED.
Некластерный (плотный индекс). До 249 для таблицы. Если в таблице не существует кластерный индекс, то ссылки указывают на записи в основной области. Если в таблице имеется кластерный индекс, то все некластерные индексы ссылаются на записи кластерного индекса. Это позволяет избежать перестройку некластерных индексов при упорядочении записей (как это требует кластерный индекс). Если допускаются неуникальные значения ключей, то сервер БД добавляет к ним дополнительные значения, делая их уникальными.
Уникальность:
Уникальный индекс (кластерный или некластерный) гарантирует уникальность значений в индексируемом столбце. Вставка дубликатов будет отклоняться. Вместо требования уникальности индекса можно использовать ограничения PRIMARY KEY или UNIQUE.
Не уникальный индекс. Не гарантирует уникальность значений.

Длинные (символьные и составные) ключи снижают производительность и требуют затрат памяти (значения ключей дублируются в индексе)
Индексирование увеличивает время вставки, поэтому индексирование должно быть оправданным. Для часто изменяемых столбцов следует использовать некластерные индексы.

Слайд 21

Индексы в Transact-SQL
Способы задания индексов:
Автоматическое создание при объявлении первичного ключа. Объявление

PRIMARY KEY создает кластерный индекс.
Автоматическое создание при объявлении ограничения целостности UNIQE. Объявление UNIQUE создает уникальный некластерный индекс. Их может быть более одного.
Команда CREATE INDEX

Слайд 22

Индексы в Transact-SQL
Сокращенное описание
CREATE [ UNIQUE ] [ CLUSTERED | NONCLUSTERED

] INDEX index_name
ON table ( column [ ASC | DESC ] [ ,...n ] )
[ WITH ( [ ,...n ] ) ]

::=
{
PAD_INDEX = { ON | OFF }   |
FILLFACTOR = fillfactor   |
IGNORE_DUP_KEY = { ON | OFF }
}

index_name – имя индекса должно быть уникальным в пределах одной таблицы
PAD_INDEX – резервировать свободное пространство на страницах (используется вместе с FILLFACTOR. Используется только при перестроении индекса
FILLFACTOR – задает процент (от 1 до 100) заполнения страниц. Используется только при перестроении индекса
IGNORE_DUP_KEY – используется только для уникальных индексов. Если параметр указан, то дубликаты игнорируются. Если параметр не указан, то откатывается вся транзакция

Физические модели баз данных

Содержание

Внешние устройства хранения информацииУстройства произвольного доступа (например, магнитные диски). Файлы с

Физическая модельДалее будем рассматривать только файлы с постоянной длиной записиУпрощение: для

Физическая модельЛогическая запись (запись) – кортеж отношенияФизическая запись (страница, блок) –

Физическая модельНа производительность СУБД влияют:Организация файла: распределение данных по записям и

Последовательная неупорядоченная организация файлаПоследовательный неупорядоченный файл (куча) – простейший тип структуры

Метод дихотомииНа примере упорядоченного массива:Найти срединный элемент. Выбирается та половина на

Последовательная упорядоченная организация файлаВ последовательных упорядоченных файлах записи упорядочены по одному

Хеширование данныхОсновная идея – записи в файле прямого доступа находятся в

Хеширование данныхКоллизия: h(Ki) = h(Kj)Значения таких ключей – «синонимы»Способы разрешения коллизий:Область

Хеширование данныхНесвязанная область переполненияОсновная областьОбласть переполнения (последовательное неупорядоченное хранение)Адрес = PK

Хеширование данныхСвязанная область переполненияОбласть переполнения (связанный список)Основная область

Хеширование данныхСвободное замещениеОсновная областьвставкапредыдущийследующий

Индексные файлыСнижение времени поиска:Бинарный поискЧасть индексного файла – в оперативной памяти

Файлы с плотным индексомИндексный файлОсновная областьСтраница 1Страница 2Новая записьНовая индексная запись

Файлы с неплотным индексомИндексный файлОсновная областьСтраница 1Страница 2Новая запись

Многоуровневые индексыИндексный файл 2Основная областьИндексный файл 1

Вторичные ключиВторичный ключ – произвольный набор атрибутов, которому соответствует набор искомых

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

Индексы в Transact-SQLВиды индексов:Кластерный (неплотный индекс). Один на таблицу. Для первичного

Индексы в Transact-SQLСпособы задания индексов:Автоматическое создание при объявлении первичного ключа. Объявление

Индексы в Transact-SQLСокращенное описаниеCREATE [ UNIQUE ] [ CLUSTERED | NONCLUSTERED

Похожие презентации