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

ФИЗИЧЕСКАЯ СТРУКТУРА ДАННЫХ

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

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

На первом этапе использования вычислительных машин (50-е годы) обработке подвергались лишь числа, представления которых в памяти вычислительной машины и внешнее представление пользователем-программистом совпадали. Это было представление в двоичной системе счисления, любое данное занимало одну ячейку памяти, не зависимо от фактического размера значения данного.

Следующий этап (60-е годы) характеризуется тем, что

логическое и физическое представления данных отличаются друг от друга.

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

На логическом уровне данные представляются в виде десятичных чисел, символов естественного языка. Разнотипные данные объединяются в структуры, которые мы ранее определили как линейные структуры (т. е. -).

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

Вместе с тем, прослеживается тенденция использования в современных системах идей и принципов физической организации данных, которые использовались в СУБД первого поколения (принцип «развития по спирали» в действии). Зная и понимая физическую организацию информации в БД можно создать более эффективную программу обработки.

Уровни рассмотрения структуры

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

Будем рассматривать возможные подходы к физической организации информации на уровнях:

· базы данных – как совокупность взаимосвязанных разнотипных записей;

· файла – как совокупность взаимосвязанных однотипных записей;

· записи – как совокупность взаимосвязанных данных.

Структуру уровня данных в рамках нашего курса можно не рассматривать, так как с точки зрения СУБД – это неделимые элементы. Отметим лишь, что в большинстве СУБД, да и языков программирования используют одни и те же типы данных (типовые структуры данных):

· символьные;

· числа: целые, с фиксированной или с плавающей точкой;

· данные типа дата и время;

·  Логические;

· текстовые и двоичные данные произвольной длины.

Структурные характеристики

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

Универсализм в пределах типа.

Основные операции над информационными элементами:

- выделение элементов определенного типа среди других (необходимы: имя, размер и адрес элемента);

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

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

-  переход к другому связанному элементу структуры – необходим адрес связанного элемента.

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

· имя элемента структуры;

· размер элемента структуры;

·  адрес элемента;

· адрес связанного элемента;

· тип внутренней структуры элемента

рассматриваемой структуры.

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

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

Анализ возможных способов физической организации информации различных уровней будем рассматривать в зависимости от:

· способа представления собственно информации об объектах предметной области хранимой в памяти компьютера;

· способа представления структурных характеристик;

· способа хранения (совместного или автономного) структурных характеристик и собственно информации.

СТРУКТУРА УРОВНЯ ЗАПИСИ

Элементами структуры являются данные.

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

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

Более подробно о кодировании значений данных было рассмотрено в разделе «Проблемы использования кодификаторов».

Наиболее часто используют два способа формирования кодов: порядковое и серийно-порядковое.

При порядковом кодировании очередному (по какому то правилу) значению символьного данного присваивается очередное значение из простой последовательности чисел.

Например, для атрибута НАЦИОНАЛЬНОСТЬ возможным значениям присваиваются трехзначные (потому, как число национальностей более 100, но не превышает 999), предварительно упорядочив значения (по алфавиту или по частоте употребления или др.) Азербайджанцы – 001, Абхазцы – 002, …., Русские – 104, …, Якуты – 132.

При серийно-порядковом кодировании применяются иерархические коды, аналогично рассмотренным нами в курсе Информационные системы иерархическим ИПЯ.

Например, для атрибута НАЦИОНАЛЬНОСТЬ

Вначале все множество возможных значений атрибута разбивается на группы по какому то признаку (например, по типу языка славяне – 1, тюрки – 2, …)

Затем внутри каждой группы свои значения: для славян – русские – 11, белорусы – 12, украинцы – 13,…., азербайджанцы – 21,…, туркмены – 22, турки – 23,….

Серийно - порядковое кодирование используется в тех случаях. Когда на вне машинном уровне желательно отразить семантику значения, чтобы родственные в каком-то смысле значения имели бы близкие коды.

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

Например, для атрибута ПОЛ: 01 – мужской, 10 – женский.

Для атрибута МЕСЯЦ: – январь, - февраль, ….., – ноябрь,

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

Представление структурных характеристик (уровень записи)

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

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

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

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

Возможны два способа хранения структурных характеристик и собственно информации об объектах – совместное и автономное.

Например, имеем следующее логическое представление записей

Ф. И.О.	Пол	Национальность
.	.	.
	М	русский
Михалков-	М	русский
.	.	.

При иллюстрации физической структуры используем следующие условности:

· каждый байт памяти будем отображать в виде одной клетки;

· оперативную память будем отображать в виде «клетчатой» таблицы шириной по 10 байт с тем, чтобы было проще адресовать байты памяти;

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

· полагаем, что для отображения имени данного достаточно 8 байт, размера данного – 1 байт, типа структуры элемента – данного – 1 байт (С – символьный, Ч – числовой), адресного указателя - 1 байт, хотя в реальной практике адрес имеет размер, равный так называемой разрядности компьютера (в 32 разрядной – 4 байта).

· при использовании адресного указателя, он располагается непосредственно за значением данного, связь которого с другим данным он и указывает.

адрес

1	Ф	И	О						11	С
11	И	В	А	Н	О	В		И	.	И
21	.	П	О	Л						1
31	С	М	Н	А	Ц	-	О	С	Т	Ь
41	7	С	Р	У	С	С	К	И	Й	Ф
51	И	О						26	С	М
61	И	Х	А	Л	К	О	В	-	К	О
71	Н	Ч	А	Л	О	В	С	К	И	Й
81		А	.	С	.	Далее значения
91	структурных характеристик и собственно информации (пол и нац-ость) второй записи - о Михалкове – и т. д.
101

Это вариант совместного хранения структурных характеристик имя, размер, тип структуры элемента и собственно информации, а также последовательно-смежного размещения непосредственно связанных данных

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

Вариант автономного хранения структурных характеристик имя, размер, тип структуры данного и последовательно-смежного размещения связанных элементов – данных.

Но тогда они должны быть одинаковы для одноименных данных.

Структурные характеристики

Адрес

байта

1	Ф	И	О						26	С
11	П	О	Л						1	С
21	Н	А	Ц	-	О	С	Т	Ь	15	С
31	51	- адрес, где начинается собственно информация
41
51	И	В	А	Н	О	В		И	.	Й
61
71							М	Р	У	С
81	С	К	И	Й
91			М	И	Х	А	Л	К	О	В
101	-	К	О	Н	Ч	А	Л	О	В	С
111	С	К	И	Й	М	Р	У	С	С	К
121	Й									…

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