Каждая БД состоит из файлов. Файлы состоят из логических записей. Данные хранятся во внешней памяти на соответствующих носителях (магнитные ленты, диски, "винчестеры" и др.). Каждый файл представляется в виде одного или нескольких блоков (страниц) данных. В одном блоке может быть одна логическая запись, несколько записей (блокированные записи), часть ее (сегмент). В последнем случае сегменты одной записи хранятся в разных блоках. Адресные ссылки между сегментами позволяют выбрать запись целиком в оперативную память.
Обмен данными между внешней я оперативной памятью выполняется блоками, т.е. блок - минимальная единица обмена между оперативной памятью и внешним носителем. При чтении с внешнего носителя блок данных размещается в буферный участок памяти. Несколько буферов образуют буферный пул. Каждый байт в блоке пронумерован (0, 1, 2,...). Номер байта блока, с которого начинается запись, определяет относительный адрес записи файла в блоке.
В качестве адресов записей файла во внешней памяти используют: машинный адрес, относительный адрес, ключ записи. В качестве относительного адреса записи файла используют ее номер по порядку (внутрисистемный номер) в файле, либо комбинацию номера блока и относительного адреса в блоке, либо номер блока и значение ключа. Во многих системах при вводе записи ей присваивается уникальный системный идентификатор - ключ базы данных. Ключ БД не следует отождествлять с ключом записи. Последний задается и используется пользователем (прикладной программой).
Данные, которые присутствуют в физической БД, но отсутствуют в логической БД, называют прозрачными. Такие данные никогда не представляются пользователю (например, адресные ссылки, ключ БД, различные счетчики в т.п.,). Данные, которые присутствуют в логической БД, но отсутствуют в физической БД называются виртуальными (например, возраст).
Каждая физическая запись, соответствующая логической, состоит обычно из двух частей - служебной и информационной. Поля служебной (прозрачной) части используются СУБД для идентификации записи, задания ее типа, хранения признака логического удаления, для кодирования значений элементов, для установления структурных связей между записями. Никакие пользовательские программы не имеют доступа к служебной части записи.
Поля информационной части содержат значения элементов данных логической записи. При этом существует два основных способа размещения значений элементов в физической записи.
1. Размещение с заранее предписанных позиций предполагает, что значение элемента в каждом экземпляре записи появляется с одной и той же позиций, определенной в описании БД.
2. Размещение с разделителями позволяет не хранить в памяти незначащие символы. Здесь элементы отделяются друг от друга разделителями (специальными кодами, часто со смысловой негрузкой, например, с указанием длины размещенного за ним значения). Если длина элементов варьируется, то память расходуется более экономно, но требуются дополнительные затраты времени м рас кодировку записи. Записи могут быть фиксированной и переменной длины.
Записи обычно размещаются в блоках плотно, без промежутков, последовательно одна за другой. В блоке часть памяти отводится также для служебной информации о блоке: относительные адреса свободных участков памяти, указатели на следующий блок и т.д.
Обычно блоки заполняются не полностью. Оставшаяся часть блока остается некоторое время незаполненной (зарезервированной). В дальнейшем эта область заполняется при увеличении (расширении) записей, хранящихся в блоке, или при поступлении в систему новых записей, которые в соответствии со значениями их ключей (или по другим условиям) надо поместить в одном блоке с уже хранящимися записями. По истечении некоторого времени блок заполняется полностью. Для хранения новых поступающих данных, которые должны были бы попасть в этот блок, выделяется дополнительный блок памяти в области переполнения. Записи, которые должны были размещаться в одном блоке, связываются специальными указателями в одну цепь. Файл периодически реорганизуется: при необходимости файлу добавляется требуемое количество блоков в основной внешней памяти и выполняется требуемая перекомпоновка записей, с целью освобождения области переполнения внешней памяти. Необходимое количество блоков определяется выражением:
где N3 – количество записей в файле;
V3, Vбл – объем записи и блока, байт; (r < 1) – незаполненная часть блока.
Все блоки каждого файла пронумерованы (1,2,3,...,Nб) и система определяет требуемый блок по имени файла и номеру блока. Если файл состоит из записей фиксированной длины, записи организованы последовательно и имеют внутри файла системный номер, то по этому номеру i вычисляют номер блока, в котором находится запись:
.
Среднее время выполнения операции обмена t0 зависит от типа устройства внешней памяти ( от его характеристик) и от размера блока:
T0 = Vбл tp + tпод,
где tp – время считывания одного байта, tпод - время подготовки устройства к обмену.
Время поиска данных в файле tп определяется следующим образом
tп = x0 t0 + xc tc ,
t0 – среднее время выполнения ( в процессоре) одной операции сравнения; xc - количество операций сравнения ( в оперативной памяти); x0 – количество операций обмена.
Если tc << t0 , то время поиска в основном определяется временем, затрачиваемым на обмен с внешней памятью.
На скорость потока данных в файле наибольшее влияние оказывает следующие характеристики файла и технических устройств внешней памяти, использованных для его организации: объем блока (в байтах); объем файла (в байтах); количество записей в блоке файла n збл ; количество записей в блоке индекса; количество блоков в файле данных nблф ; доля резервируемой части блока r; длина записи; размер записи (в байтах) Vз ; длина ключевого поля в записи; число записей файла, удовлетворяющих условию поиска Q; среднее число блоков переполнения на один блок файла; среднее время обмена t0.
.