Файловые структуры организации данных
В системах БД, файловая структура используется для хранения информации во внешней памяти, определяют их классификацию. В файле всегда можно определить:
первую запись
последнюю
текущую
предшествующую текущей
следующей за текущей
Иерархическая файловая структура
Для каждого файла можно получить следующую информацию:
имя файла
тип файла
размер записи
число занятых физ блоков
базовый начальный адрес
ссылка на сегмент расширения
способ доступа
Разрешение коллизий с помощью области переполнения
При выборе этой стратегии область хранения разбивается на две части: основную область и область переполнения.
Для каждой новой записи вычисляется значение хеш-функции, которое определяет адрес ее расположения, и запись заносится в основную область в соответствии с полученным значением хеш-функции.
Если вновь вносимая запись имеет такое же значение функции хеширования, которое использовала другая запись, уже имеющаяся в БД, то новая запись заносится в область переполнения на первое свободное место, а в записи-синониме, которая находится в основной области, делается ссылка на адрес вновь размещенной записи в области переполнения. Если же уже существует ссылка в записи-синониме, которая расположена в основной области, то новая запись получает дополнительную информацию в виде ссылки и уже в таком виде заносится в область переполнения.
При таком алгоритме время размещения любой новой записи составляет не более двух обращений к диску, с учетом того, что номер первой свободной записи в области переполнения хранится в виде системной переменной.
Разрешение коллизий методом свободного замещения
При этой стратегии файловое пространство не разделяется на области, но для каждой записи добавляются два указателя: указатель на предыдущую запись в цепочке синонимов и указатель на следующую запись в цепочке синонимов. Отсутствие соответствующей ссылки обозначается специальным символом, например нулем. Для каждой новой записи вычисляется значение хеш-функции и, если данный адрес свободен, запись попадает на заданное место и становится первой в цепочке синонимов.
Хеш-функция или функция свёртки — функция, осуществляющая преобразование массива входных данных произвольной длины в выходную битовую строку установленной длины, выполняемое определённым алгоритмом.
Синоним - как и в грамматике но ещё определять альтернативные имена для уже существующих объектов. Синонимы работают подобно алиасам столбцов или таблиц.
Если запись, которая занимает требуемое место, не является первой записью в цепочке синонимов, значит, она занимает данное место «незаконно» и при появлении «законного владельца» должна быть «выселена», т.е. перемещена на новое место.
После перемещения «незаконной» записи вновь вносимая запись занимает свое законное место и становится первой записью в новой цепочке синонимов.
Индексные файлы и файлы с плотным индексом
Индексные файлы можно представить как файлы, состоящие из двух частей. Сначала идет индексная область, которая занимает некоторое целое число блоков, а затем идет основная область, в которой последовательно расположены все записи файла.
В некоторых системах индексными файлами называются также и файлы, организованные в виде инвертированных списков, которые используются для доступа по вторичному ключу. В зависимости от организации индексной и основной областей различают два типа файлов: с плотным индексом (индексно-прямые файлы) и с неплотным индексом (индексно-последовательные файлы).
Файлы с плотным индексом В этих файлах основная область содержит последовательность записей одинаковой длины, расположенных в произвольном порядке, а структура индексной записи в них имеет следующий вид:
Значение ключа |
Номер записи |
Здесь значение ключа — это значение первичного ключа, а номер записи – это порядковый номер записи в основной области, которая имеет данное значение первичного ключа. При организации хранения данных в виде файлов с плотным индексом число обращений к диску при добавлении новой записи определится по формуле
Тn = log2 Nинд. обл. + 1 + 1 + 1.
Смысл формулы заключается в следующем: число обращений определяется числом обращений к индексной области плюс одно обращение к основному блоку, плюс одно обращение для изменения индексного блока и плюс одно обращение для занесения записи в основную область.
Таким образом, в файлах с плотным индексом при обработке одной записи требуется дополнительно два обращения к дисковому пространству компьютера.