Модель внешней памяти

Данные хранятся во внешней памяти на магнитных дисках, магнитных лентах и т.д., а их обработка выполняется в оперативной памяти ЭВМ. Поэтому при обработке некоторые порции данных пересылаются из внешней памяти в оперативную либо наоборот [17].

При больших объемах данных в БД может потребоваться несколько томов внешней памяти. Однако обмен между внешней и оперативной памятью выполняется небольшими порциями данных – обычно объемом не более нескольких сотен байт. С этой целью внешняя память разбивается на части, называемые блоками или страницами. Данные пересылаются блоками. Операции пересылки еще называют обменом данными между внешней и оперативной памятью. Такой обмен называется чтением блока, а в обратном направлении - записью блока.

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

Для организации каждого файла в зависимости от его размера во внешней памяти ему выделяется от одного до

блоков, где размещаются записи файла. Предположим, что в одном блоке размещаются записи только одного файла. В зависимости от соотношения объемов записей и блоков может оказаться, что в одном блоке размещается либо одна, либо несколько записей файла, либо одна запись размещается в нескольких блоках. Обычно запись занимает несколько десятков байт.

Каждый байт в блоке пронумерован:

. Номер байта блока, с которого начинается запись, определяет относительный адрес записи файла в блоке.

В качестве адресов записей файла во внешней памяти используют: машинный адрес, относительный адрес, ключ записи [17].

В качестве относительного адреса записи файла используют ее номер по порядку (внутрисистемный номер) в файле либо комбинацию таких составляющих адреса, как номер блока и относительный адрес в блоке, ибо номер блока и значение ключа.
В последнем случае, после считывания блока в буфер оперативной памяти, доступ к записи в буфере осуществляется с помощью какого-либо метода поиска записей в файле по значению ключа.

При чтении записи из блока, который уже находится в буфере, обмен с внешней памятью не выполняется. Во многих системах при вводе записи ей присваивается уникальный системный идентификатор – ключ базы данных.

Запись обычно состоит из:

1) служебных полей, в которых хранятся указатели, реализующие связи с другими записями, и другая информация, необходимая для организации управления файлом,

2) полей хранимых данных.

Записи могут быть фиксированной и переменной длинны. Записи размещаются в блоках плотно, без промежутков, последовательно одна за другой. В блоке часть памяти отводится для служебной информации о блоке: относительные адреса свободных участков памяти, указатели на следующий блок и т.д.

Если файл базы данных состоит из записей фиксированной длинны, то в одном блоке может разместиться

записей:

,

где

- обозначает целую часть числа;

- соответственно объем блока и записи в байтах.

Однако обычно блоки заполняются не полностью, например, наполовину. Оставшаяся область блока остается некоторое время при работе системы незаполненной (зарезервированной). В дальнейшем эта область заполняется при расширении (увеличении) записей, хранящихся в блоке, или при поступлении в систему новых записей, которые в соответствии со значениями их ключей или по другим условиям необходимо поместить в одном блоке с уже хранящимися записями. По истечении некоторого времени блок заполняют полностью.

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

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

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

Поэтому периодически файл реорганизуется: при необходимости файлу добавляется требуемое количество блоков в основной области памяти и выполняется требуемая перекомпоновка записей. При этом исходят из расчета, чтобы можно было освободить область переполнения, а все записи разместить в блоках основной области, причем, в каждом блоке разместить записи последовательно и в таком количестве, чтобы

-я часть блока осталась незаполненной. В этом случае требуемое количество блоков:

где

< 1 – незаполненная часть блока;

- количество записей в файле.

Считается, что все блоки каждого файла пронумерованы:

и система определяет требуемый блок по имени файла и номеру блока. Если файл состоит из записей фиксированной длины, записи организованы последовательно и имеют внутри файла системный номер, то по этому номеру вычисляют номер блока, в котором находится запись:

,

Среднее время выполнения операций обмена зависит от типа устройства внешней памяти (от его характеристик) и от размера блока:

,

где

- среднее время выполнения операции обмена;

- время считывания, приведенное к одному байту (т.е. время считывания одного байта);

- время подготовки устройства к выполнению операции обмена.

Время поиска данных в файле:

,

где

- время выполнения операции поиска;

- среднее время выполнения в процессоре одной операции сравнения;

- количество операций обмена;

- количество операций сравнения.

Если

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

На скорость поиска данных в файле наибольшее влияние оказывают следующие характеристики файла и технических устройств внешней памяти, использованных для его организации [17]:

–       объем блока;

–       объем байта;

–       количество записей в блоке файла

;

– количество записей в блоке индекса;

– количество блоков в файле данных

;

– доля резервируемой части блока

( при начальной организации данных в файле);

– длина поля, отведенного для указателя;

– количество записей в файле

;

– размер записи

;

–       длина ключевого поля записи;

–       число записей файла, удовлетворяющих условию поиска Q;

–       среднее число блоков переполнения на один блок файла;

–       среднее время обмена

.

На рис. 3.7 изображен файл со следующими характеристиками:

=10;

=4;

=0,5. Записи файла описываются схемой:

, т.е.

=4. При начальной загрузке при таких характеристиках для организации файла требуется 5 блоков.

Содержание раздела