Предыдущая страница реферата | 1  2  3  4  5  6  7 | Следующая страница реферата

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

Стоимость операций со внешней памятью.

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

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

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

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

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

Хранение данных в файлах.

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

Файл будет рассматриваться как последовательность записей, причём каждая запись состоит из одной и той же совокупности полей. Поля могут иметь либо фиксированную длину (заранее определённое количество байт), либо переменную. Файлы с записями фиксированной длины широко используются в системах управления базами данных для хранения данных со сложной структурой. Файлы с записями переменной длины, как правило, используются для хранения текстовой информации; в языке Pascal такие файлы не предусмотрены. В этом разделе будем иметь дело с полями фиксированной длины; рассмотренные методы после определённой

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

Будут рассмотрены следующие операторы для работы с файлами.

INSERT вставляет определённую запись в определённый файл.

DELETE удаляет из определённого файла все записи, содержащие указанные значения в указанных полях.

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

RETRIEVE отыскивает все записи, содержащие указанные значения в указанных полях.

Простая организация данных.

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

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

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

(i+1)-ю запись.

Если записи являются закреплёнными, следует воспользоваться каким-то другим подходом. Мы должны как-то помечать удалённые записи, но не должны смещать оставшиеся на место удалённых (и не должны вставлять на их место новые записи). Таким образом выполняется логическое удаление записи из файла, но её место в файле остаётся незанятым. Это нужно для того, чтобы в случае появления указателя на удалённую запись мы могли, во-первых, понять, что указываемая запись уже удалена, и, во-вторых, предпринять соответствующие меры (например, присвоить этому указателю значение NIL, чтобы в следующий раз не тратить время на его анализ).

Существуют два способа помечать удалённые записи.

Заменить запись на какое-то значение, которое никогда не может стать значением «настоящей» записи, и, встретив указатель на какую-либо запись, считать её удалённой, если она содержит это значение.

Предусмотреть для каждой записи специальный бит удаления; этот бит содержит 1 в удалённых записях и 0 – в «настоящих» записях.

Рекомендуем скачать другие рефераты по теме: реферат китай курсовые работы, бесплатные шпаргалки по праву.





Предыдущая страница реферата | 1  2  3  4  5  6  7 | Следующая страница реферата