Файлы с плотным индексом, или индексно-прямые файлы.

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

Значение ключа

Номер записи

Здесь значение ключа — это значение первичного ключа, а номер записи – это порядковый номер записи в основной области, которая имеет данное значение первичного ключа.

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

где N – число элементов.

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

В соответствии с формулой число обращений к диску при поиске записи определится следующим образом:

где – число индексных блоков, в которых размещаются все записи.

Учитывая что после поиска записи в индексном блоке нужно еще раз обратиться к основной области, в формуле, добавилась единица (+1).

В табл. 1 представлена схема организации такого файла на дисковом пространстве (фоном выделены свободные зоны).

Таблица 1
Схема организации файла с плотным индексом
Блок	Ключи	Ссылки на № записи	Свободная зона	Области
Блок 1	01-10/01			Индексная область
02-20/02
03-20/00
Блок 2	06-40/00
07-50/01
08-30/01
Блок 3	10-44/01
11-44/02
09-35/01
Блок 4	17-20/03
18-40/02
20-35/02
Номер записи	Ключ	Содержание	Основная область
	10-44/01	Математика
	11-44/02	Физика
	01-10/01	Информатика
	02-20/02	Теория информации
	03-20/00	Базы данных
	09-35/01	Интерфейс АСОиУ
	06-40/00	Защита информации
	07-50/01	АСТПП и САПР
	08-30/01	Языки программирования
	17-20/03	Операционные системы
	18-40/02	Цифровые сети интегрального обслуживания
	20-35/02	Технологии программирования

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

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

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

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

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

Т_n = log₂ N_{инд. обл.} + 1 + 1 + 1.

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

Таким образом, в файлах с плотным индексом при обработке одной записи требуется дополнительно два обращения к дисковому пространству компьютера.

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

Дата добавления: 2015-10-21