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

с постоянной длиной записи. Местоположение записи файла определяется адресом.
Устройства последовательного

доступа (например, стример). Файлы с переменной длиной записи

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

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

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

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

БД

страницы

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

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

структуры файла
Записи размещаются в файле в том порядке, в котором

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

на которая должна содержать заданное значение (по результатам сравнения значения

со значениями левой и правой границ половин)
Если элемент не является границей, то в качестве исходного элемента рассматривается выбранная половина. Переход к п.1.

Среднее количество операций ~ln2(n), а последовательный поиск ~n

16?

итерации

одному или нескольким полям
Поиск выполняется быстро методом дихотомии (бинарный поиск)
Операция

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

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

в «перемешанном» порядке (hash = путаница): записи с близкими значениями

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

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

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

коллизий:
Область переполнения:
несвязанная
связанная
Свободное замещение

PK mod5
PK

памяти

запись

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

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

INSERT и DELETE, но и при UPDATE

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

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

Уникальность:
Уникальный индекс (кластерный или некластерный) гарантирует уникальность значений в индексируемом столбце. Вставка дубликатов будет отклоняться. Вместо требования уникальности индекса можно использовать ограничения PRIMARY KEY или UNIQUE.
Не уникальный индекс. Не гарантирует уникальность значений.

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

Объявление PRIMARY KEY создает кластерный индекс.
Автоматическое создание при объявлении ограничения

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

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 – используется только для уникальных индексов. Если параметр указан, то дубликаты игнорируются. Если параметр не указан, то откатывается вся транзакция

int, c int);
CREATE UNIQUE CLUSTERED INDEX Idx1 ON t1(c);

Простой некластерный индекс
CREATE INDEX IX_ProductVendor_VendorID
ON ProductVendor (VendorID);

Составной некластерный индекс
CREATE NONCLUSTERED INDEX IX_SalesPerson_SalesQuota_SalesYTD ON SalesPerson (SalesQuota, SalesYTD);

Уникальный некластерный индекс
CREATE UNIQUE INDEX AK_UnitMeasure_Name ON Production.UnitMeasure(Name);

Уникальный индекс, игнорирующий дубликаты
CREATE UNIQUE INDEX AK_Index ON Test (C2)
WITH (IGNORE_DUP_KEY = ON);

Автоматическое создание кластерного индекса
CREATE TABLE t1 (a int, b int, c int PRIMARY KEY);