Физическая структура данных (стр. 7 )

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

Инвертированное представление «идет» не от объекта, а от значения данных. Запись при таком представлении: составляют список идентификаторов (ключей) объектов, которые обладают одним и тем же значением данного.

ПРЯМОЕ

Физич. адрес	Номер физич. записи	Ф. И.О.	Пол	Национальность
1	25		М	русский
41	96		Ж	украинка
81	33		М	белорус
121	330		М	русский
161	111		Ж	азербайджанка
201	110		Ж	украинка
241	100		М	русский
281	112		Ж	еврейка
321	35		М	русский

ИНВЕРТИРОВАННОЕ

Значение атрибута	Номер физич. записи
М	25,33,330,100,35
Ж	96,111,110,112
азербайджанка	111
белорус	33
еврейка	112
русский	25,330,100,35
украинка	96,110
	25
	33
	330
	96
	111
	110
	100
	112
	35

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

Физич. адрес	Номер физич. записи	Ф. И.О.	Пол	Национальность
1	25		М	русский
41	96		Ж	украинка
81	33		М	белорус
121	330		М	русский
161	111		Ж	азербайджанка
201	110		Ж	украинка
241	100		М	русский
281	112		Ж	еврейка
321	35		М	русский

Вст.	350		М	русский
Удал

Замена у (№ записи=96) значение национальности украинка на еврейка

Значение атрибута	Номер физич. записи
М	25,33,330,100,35, 350
Ж	96,111,110,112
азербайджанка	111
белорус	33
еврейка	112,96
русский	25,330,100,35, 350
украинка	96,110
	25
	33
	330
	96
	111
	110
	100
	112
	35
	350

Кстати, как физически организовать такой файл?

Для атрибутов, число возможных значений которых соизмеримо с числом записей в файле использование не эффективно (см. ФИО)

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

Эффективно может быть реализована связь между различными файлами, но это уже структура уровня БД.

В практике СУБД инвертированное представление используется лишь как дополнительное к прямому представлению, реализуемое для данных, значения которых часто используются при поиске и связывании объектов, например, в системах ADABAS (ассоциатор - для поиска и связи) и FoxPro (связь типа One-to - many).

Инвертированное представление

Это тот же индексный файл, но в специальной форме.

Значение атрибута	Номер физич. записи
Ж	96,111,110,112
М	25,33,330,100,35
азербайджанка	111
белорус	33
еврейка	112
русский	25,330,100,35
украинка	96,110
	25
	33
	330
	96
	111
	110
	100
	112
	35

Пол	№ записи
Ж	96
Ж	111
Ж	110
Ж	241
М	25
М	33
М	330
М	100
М	281

Это были примеры т. н. плотного индекса. Если число записей в файле велико – используется разряженный индекс. Первое использование разряженного индекса было в 70-е годы, когда стали адресоваться физические блоки на диске. Это была Индексно-последовательная организация файла

Индексно-последовательная организация файла

1. Физически файл размещается в множестве физических блоков (страниц). Чаще всего это дорожки диска. В общем – адресуемые физические непрерывные участки внешней памяти

2. Файл упорядочивается по значению некоторого атрибута (группы атрибутов) – ключ упорядочения.

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

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

Если индексный файл тоже велик, то может создаваться индекс второго порядка (над первичным индексом)

1 Пусть имеем файл, записи которого размером 50 байт

2 Файл размещается на диске, состоящем из физических блоков (страниц) размером 4096 байт:

- 96 байт под описание блока (номер блока, тип блока, номер следующего в типе, адрес 1-го пустого байта);

- 4000 байт под записи – 80 штук может войти

Файл о студентах

Блоки диска

1	2		n-1	n
№ зач. 80-го студ-та	№ зач. 160-го студента		№ зачетки (n-1)*80

№ зач. (ключ) Индексный файл

№ бл	Знач. ключа
1	00
2	00
…
102	08
103	08
….

00_________

………….

0025__________

00__________

………….

0022__________

00_________

…………..

08________

08_________

Индекс в виде В-дерева (бинарный)

1. Файл упорядочивается и последовательно-смежно размещается по физическим блокам как и в предыдущем примере.

2. Индекс корневой содержит значение ключа для записи, которая располагается в центре файла и адресные ссылки на аналогичные индексы для первой и второй половины файла т. е. значение ключа для записи, располагаемой в середине первой половины и в середине второй половины.

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

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

- файл физически может быть упорядочен только по одному ключу;

проблемы при вставке и удалении записей

Файл с прямым доступом

По значению ключа вычисляется:

- точно адрес любой записи.

- адрес физического блока, где располагается запись (метод хеширования).

+ очень быстрый доступ по ключу

- трудно подобрать алгоритм, позволяющий избежать

пустот в памяти;

должен быть цифровой ключ.

ОБОЩЕНИЕ ДАЛЕЕ

Типовые способы организации и методы доступа файлов

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

1 Файлы последовательного доступа

Последовательно-смежная организация - последовательный доступ к хранимой информации. Обычно упорядочивается по возрастанию или убыванию значения 1 или нескольких атрибутов – по ключу упорядочения (не путать с ключом файла)

2 Файлы прямого доступа

Относительно произвольное размещение - прямой доступ с расчетом адреса хранения записи файла по значению ключа записи (рандомизация, хэширование – спец. алгоритм – рандомизирующий модуль, например по значению личного номера работника А= (№ - 1)*размер записи

3 Индексные файлы:

3.1 Плотный индекс – с помощью таблицы

значение ключа – номер(адрес) записи

(в реляционных СУБД – основной способ)

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

№ блока - значение ключа последней записи в блоке

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

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

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

- индексы второго уровня содержат аналогичные элементы, но каждый для своей части файла;

- аналогично строятся двоичные индексы до тех пор, пока адресация доходит до единственных физических блоков.

6 Инвертированная организация

7 Цепная (списковая) организация – адресные указатели на адрес связанной записи:

Структура БД

1 Элементы - записи разных файлов (разных типов – линейных структур)

2 Связи:

- последовательно-смежно (только для иерархических структур)

- прямые адресные ссылки на связанную запись

- неявное по совпадению значений атрибутов

Пример простой ИС