Файловые структуры, используемые для хранения данных в БД
На устройствах последовательного доступа (магнитофоны, стримеры) могут быть организованы файлы только последовательного доступа. Файлы с переменной длиной записи также всегда являются файлами последовательного доступа и могут быть организованы двумя способами:
- конец записи отмечается специальным маркером;
- в начале каждой записи записывается ее длина.
Файлы с постоянной длиной записи, расположенные на устройствах прямого доступа (магнитные, оптические диски), являются файлами прямого доступа. В этих файлах физический адрес расположения нужной записи может быть вычислен по номеру записи (NZ).
Для файлов с постоянной длиной записи адрес размещения записи с номером NZ может быть вычислен по формуле:
BA+( NZ -1)*LZ+1,
где BA – базовый адрес, LZ – длина записи.
Файлы прямого доступа обеспечивают наиболее быстрый доступ к произвольным записям, и их использование является наиболее перспективным в системах БД.
Однако чаще всего в БД необходим поиск по ключам, а не по номеру записи, и номер записи, необходимый для прямого доступа, в этом случае неизвестен. При организации файлов прямого доступа в некоторых случаях возможно построение функции, которая по значению ключа К однозначно вычисляет номер записи (номер записи файла) NZ=F(K).
Часто не удается построить взаимно-однозначное соответствие между значениями ключа и номерами записей, поэтому применяют различные методы хэширования; создают специальные хэш-функции.
Общей идеей методов хэширования является применение к значению ключа некоторой функции свертки (хэш-функции), вырабатывающей значение меньшего размера. Свертка значения ключа затем используется для доступа к записи.
В самом простом, классическом случае, свертка ключа используется как адрес в таблице, содержащей ключи и записи. Основным требованием к хэш-функции является равномерное распределение значений свертки. При возникновении коллизий (одна и та же свертка для нескольких значений ключа) образуются цепочки переполнения. Новая запись заносится в область переполнения на первое свободное место, а в записи-синониме (с тем же значением хэш-функции), которая находится в основной области, делается ссылка на адрес вновь размещенной записи в области переполнения. Главным ограничением этого метода является фиксированный размер таблицы. Если таблица заполнена слишком сильно или переполнена, но возникнет слишком много цепочек переполнения, и главное преимущество хэширования - доступ к записи почти всегда за одно обращение к таблице - будет утрачено. Расширение таблицы требует ее полной переделки на основе новой хэш-функции (со значением свертки большего размера).
В случае баз данных такие действия являются абсолютно неприемлемыми. Поэтому обычно вводят промежуточные таблицы-справочники, содержащие значения ключей и адреса записей, а сами записи хранятся отдельно. Тогда при переполнении справочника требуется только его переделка, что значительно проще.
Несмотря на высокую эффективность хэш-адресации, в файловых структурах не всегда удается найти соответствующую функцию, поэтому при организации доступа по первичному ключу широко используются индексные файлы. Индексные файлы можно представить как таблицы указателей к основному файлу с записями, причем для одного основного файла можно построить несколько индексных по различным ключам.
Различают два типа индексных файлов: с плотным индексом (индексно-прямые) и с неплотным индексом (индексно-последовательные) .
Структура файлов с плотным индексом имеет вид:
| Значение ключа | Номер записи в основном файле |
Записи в основном файле расположены в произвольном порядке. Такие файлы строятся для первичных ключей и в них не может быть двух записей, имеющих одинаковые значения первичного ключа. Все записи в индексном файле упорядочены по значению ключа, поэтому для поиска в индексном файле можно применить бинарный или двоичный поиск.
Файлы с неплотным индексом строятся для основных файлов, в которых записи упорядочены по ключу и структура индексных файлов имеет вид:
| Значение ключа первой записи блока | Номер блока с этой записью в основном файле |
В индексном файле ищется нужный блок по заданному значению первичного ключа. Так как все записи упорядочены, то значение первой записи блока позволяет быстро определить, в каком блоке находится искомая запись. Все остальные действия по поиску проходят в основном файле.
Наиболее популярным подходом к организации индексов в базах данных является использование техники B-деревьев. С точки зрения внешнего логического представления B-дерево - это сбалансированное дерево во внешней памяти. Сбалансированность означает, что длина пути от корня дерева к любому его листу одна и та же. Построение В-деревьев связано с простой идеей построения индекса над уже построенным индексом. Если построить файл с неплотным индексом, то, рассматривая его как основной файл, над которым надо снова построить файл с неплотным индексом, а потом снова над новым индексом строим следующий и так до того момента, пока не останется всего один индексный блок.
Если индексные файлы используются для ускорения доступа по первичному ключу, то для ускорения доступа по вторичному ключу используются структуры, называемые инвертированными списками. Вторичными ключами является атрибут или набор атрибутов, которому соответствует несколько искомых записей. Например, для таблицы «Книги» вторичным ключом может служить место издания, год издания. Множество книг могут быть изданы в одном месте, и множество книг могут быть изданы в одном году.
Инвертированный список в общем случае – это трехуровневая индексная структура. На первом уровне находится файл или часть файла, в которой упорядоченно расположены значения вторичных ключей. Каждая запись с вторичным ключом имеет ссылку на номер первого блока в цепочке блоков, содержащих номера записей с данным значением вторичного ключа. На втором уровне находится цепочка блоков, содержащих номера записей с одним и тем же значением вторичного ключа. При этом блоки второго уровня упорядочены по значениям вторичного ключа. На третьем уровне находится основной файл с записями. Представим механизм доступа к записям по вторичному ключу:
Шаг_1. В области первого уровня ищется заданное значение вторичного ключа;
Шаг_2.По ссылке считываются блоки второго уровня, содержащие номера записей с заданным значением вторичного ключа;
Шаг_3. В рабочую область пользователя прямым доступом загружается содержимое всех записей с заданным значением вторичного ключа.
Для одного основного файла может быть создано несколько инвертированных списков по разным вторичным ключам. Однако при модификации основного файла требуется внести изменения во все инвертированные списки. Поэтому можно утверждать, что построение инвертированных списков ускоряет процесс доступа только в том случае, если БД стабильна и ее содержимое не изменяется.
Для моделирования связей на файловых структурах используется принцип организации цепочек записей внутри файла и ссылки на номера записей для нескольких взаимосвязанных файлов. Цепочка – это совокупность записей, расположенных в разных местах и связанных последовательностью указателей. Структура файла с цепочкой может быть условно представлена в виде:
| Ключ | Запись | Ссылка-указатель на следующую запись |
Для моделирования отношения один-ко-многим связываются два файла, например F1 и F2, причем предполагается, что одна запись в файле F1 может быть связана с несколькими записями в файле F2. Структура файла F1 может быть условно представлена:
| Ключ | Запись | Ссылка-указатель на первую запись в файле F2, с которой начинается цепочка записей файла, связанных с данной записью файла F1 |
Структура записи файла F2 имеет вид: