Файлы с плотным индексом или индексно-прямые файлы - Проблема организации и хранения данных

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

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

Номер записи

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

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

Где N - число элементов.

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

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

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

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

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

Таблица 1. Схема организации файла с плотным индексом

Блок

Ключи

Ссылки на № записи

Свободная зона

Области

Блок 1

01-10/01

3

Индексная область

02-20/02

4

03-20/00

5

Блок 2

06-40/00

7

07-50/01

8

08-30/01

9

Блок 3

10-44/01

1

11-44/02

2

09-35/01

6

Блок 4

17-20/03

18-40/02

20-35/02

Номер записи

Ключ

Содержание

Основная область

1

10-44/01

Математика

2

11-44/02

Физика

3

01-10/01

Информатика

4

02-20/02

Теория информации

5

03-20/00

Базы данных

6

09-35/01

Интерфейс АСОиУ

7

06-40/00

Защита информации

8

07-50/01

АСТПП и САПР

9

08-30/01

Языки программирования

10

17-20/03

Операционные системы

11

18-40/02

Цифровые сети интегрального обслуживания

12

20-35/02

Технологии программирования

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

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

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

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

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

ТN = log2 NИнд. Обл. + 1 + 1 + 1.

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

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

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

Похожие статьи




Файлы с плотным индексом или индексно-прямые файлы - Проблема организации и хранения данных

Предыдущая | Следующая