Представление данных на внешних носителях

Граф

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

Дерево

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

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

Достоинства иерархических структур данных:

ü они не создают проблем с обновлением данных;

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

Недостатки иерархических структур:

- относительная трудоемкость записи адреса элемента данных;

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

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

Часто отношения между данными представляются в виде графа -совокупности точек и линий, в которой каждая линия соединяет две точки. В информатике точка получает смысл элемента струк­туры (системы, данных и пр.), а линии - смысл отношения между элементами.

f f 1

2 d 3 4 a

a c e e d

1 4 5 2

b g c b

а) б)

Примеры графов: а) неориентированный; б) ориентированный.

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

Таблица

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

Логическая запись- поименованная совокупность эле­ментарных данных, имеющая смысловую завершенность.

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

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

Поля записи связаны между собой. Связи между ними могут носить функциональный характер (значение одного поля посред­ством некоторого преобразования (правила) определяет значение другого; например, две первые цифры поля «Номер зачетной книжки» равны двум последним поля «Год поступления»), либо связи могут быть причинно-следственными (например, поле «Год рождения» определяется значением поля «Фамилия»).

Логические записи сами могут объединяться и образовывать структуры, которые определяются моделью данных. Например, сово­купность записей для всех студентов, обучающихся в одной группе, образуют массив, который называется базой данных (реляционного (описательного) типа). Обращение к базе при сохранении и исполь­зовании осуществляется по ее идентификатору (ГРУППА 101). Возможны и более высокие структурные объединения. Например, структуры, элементами которых будут базы данных (объединение баз данных по всем группам факультета). Программные системы, позволяющие создавать и использовать базы данных, называются системами управления базами данных (СУБД).

Логическая запись имеет собственный идентификатор, по ко­торому можно обратиться к записи в целом (например, порядковый номер студента в группе). Поля также имеют идентификаторы, по которым они становятся доступны для просмотра или изменения значения. Идентификатор поля строится из идентификатора базы, идентификатора записи и собственно имени поля, например, ГРУППА_101(13). Фамилия.

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

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

Многоуровневая иерархическая структура данных:

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

При хранении данных в больших массивах памяти решаются две задачи:

1) как сохранить данные в наиболее компактном виде;

2) как обеспечить к ним удобный и быстрый доступ (если доступ не обеспечен, то это не хранение).

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

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

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

Основными информационными единицами при сохранении данных на внешних носителях являются:

• логическая запись;

• физическая запись;

• файл;

• каталог (папка).

Логическая запись при хранении на внешних носителях являет­ся той же информационной единицей, что и при хранении в ОЗУ. Отличие состоит в том, что при хранении на внешнем носителе запись яв­ляется минимальным и неделимым элементом представления данных. Это означает, что после размещения записи на носителе отсутствует доступ к ее отдельным элементам, а операции переноса на носитель и считывание с него производятся целиком со всей запи­сью. Поскольку обработка записей при их хранении не происходит, не требуется и различия типов данных, т. е. запись может состоять из одного элементарного данного, группы данных или содержать структурированные данные. Единственной характеристикой от­дельной записи является ее длина, а допустимыми операциями – перенос на носитель и считывание с него.

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

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

Объединение физических записей образует файл.

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

Оформленная совокупность записей означает наличие у файла имени (идентифи­катора) и признака конца файла EOF (End-Of-File). По имени файл отыскивается на носителе, а от признака EOF устанавливается ближайшее свобод­ное место, в которое можно вести запись следующего файла, а при пересылке данных с носителя в ОЗУ по нему определяется граница информационного массива. Имя файла фактически является адресом данных. Кроме функций, связанных с адресацией, имя файла может хранить и сведения о типе данных, заключенных в нем. Требование уникальности имени очевидно – без этого невозможно гарантировать однозначность доступа к данным.

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

Описание в системе означает сохранение на носителе не только самих файлов, но и сведений о них и их размещении. Эти сведения используются в операциях с файлами. Любые файлы содержат данные, закодированные с помощью двоичного алфавита. Однако способы кодирования и назначение файлов могут быть различными. По этой причине файлам припи­сывается еще одна характеристика – тип. Тип входит в идентифи­катор файла и указывается в виде расширения имени, например, Глава_7.doc, proba.pas или calc.exe. Принципиально различными по типам следует считать программные (исполняемые) файлы и файлы данных.

Программные файлы содержат тексты программ в машинном коде; они могут быть загружены в ОЗУ и исполняться. Программные файлы имеют расширение com или ехе; к этой же категории относятся так называемые командные файлы (bath – файлы; расширение .bat), содержащие в текстовом формате команды MS DOS, которые могут последовательно выполняться как программа.

Файлы данных формируются в результате работы какой-либо программы; они не являются исполняемыми и служат только в качестве хранилищ данных. Многие программные систе­мы при формировании файлов данных приписывают им вполне определенные расширения – по ним можно установить, какой про­граммой файл создан. Например, расширения txt, doc, rtf имеют файлы, подготовленные в текстовых редакторах, bmpjpg, gif, cdr-графические файлы, pas, bas, с – файлы с текстами программ и т. д. Тип файла, как и его собственное имя, являются частью опи­сания файла и сохраняются системой, ведающей размещением файлов на носителе.

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

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

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

Итак, если после имени МД стоит :\ – двоеточие и обратная косая черта, то путь к файлу начинается с корневого каталога; например C:\ означает, что используется корневой каталог диска С. За именем корневого каталога может следовать одно или несколько имен каталогов нижнего уровня. Перед каждым из них должна быть \ – обратная косая черта.

Устройства, выполняющие операции, связанные с сохра­нением и считыванием данных на внешнем материальном носителе, называются внешними запоминающими устройствами(ВЗУ) или устройствами внешней памяти.

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

Для реализации прямого доступа на носителе должны быть обо­значены (пронумерованы) области для записи информации – такие области называются блоками. Блок, подобно ячейке ОЗУ, служит контейнером для размещения данных. Обратиться к данным для записи-считывания можно по номеру (идентификатору) блока. Операция разбиения поверхности носителя на блоки называется форматированием – она производится в обязательном порядке и предшествует использованию носителя. Блок обычно имеет строго определенную для данного носителя информационную емкость, например, для сменного магнитного диска емкостью 1,44 Мб - 512 байт. Блок может содержать только целое число фи­зических записей - из-за этого часть блока длиной меньше, чем размер записи, оказывается пустой и не используется. Например, при длине записей по 150 байт в один блок размером 512 байт по­местятся 3 записи, а 62 байта останутся свободными. На носите­лях большой емкости, например, жестких магнитных дисках (вин­честерах) блоки объединяются в группы – кластеры (например, на современных компьютерах IBM кластер охватывает 8 блоков) – запись файлов производится в них и применяется адресация по номерам кластеров (это уменьшает общее количество адресов и, следовательно, ускоряет поиск и доступ к файлу).

На дисковых носителях имена файлов хранятся отдельно от физических записей. В определенном месте диска при его форма­тировании создается специальная область, в которой располага­ется таблица размещения файлов –FAT (File Allocation Table). В эту таблицу заносятся имена и атрибуты файлов (дата и время создания, размер, атрибуты доступа), а также номер кластера, с которого начинается размещение файла. Таким образом, обра­щение к файлу происходит в два этапа: сначала с помощью фай­ловой таблицы по имени файла находится номер кластера, а за­тем считывающее – записывающая головка ВЗУ устанавливается над ним и производит операции. Содержание файловой таблицы можно просмотреть с помощью команд операционной системы.

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

Следует заметить, что, хотя организация прямого доступа к данным на ВЗУ весьма напоминает организацию произвольного доступа к ячейкам ОЗУ (то и другое производится по адресу; время доступа не зависит от адреса), между этими способами имеется различие. Из ячеек ОЗУ могут быть извлечены отдельные данные (например, элементы полей логической записи); кроме того, ОЗУ непосредственно связано с устройством обработки данных (цен­тральным процессором). При желании использовать данные с ВЗУ, во-первых, сначала весь информационный массив должен быть перенесен в ОЗУ (с ВЗУ никакой обработки не ведется); во-вторых, нужные данные в этом массиве отыскиваются последова­тельным образом.