Обзор методов доступа к файлам

Обновлено: 04.07.2024

Перечисленные методы отличаются друг от друга по двум признакам:

Эффективность хранения;
Эффективность доступа.

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

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

Физический последовательный метод доступа

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

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

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

Эффективность физического последовательного доступа очень низка. Для нахождения нужной записи производится последовательный перебор. В среднем требуется перебрать N/2 записей при общем количестве записей N.

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

Готовые работы на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту Узнать стоимость

Индексно-последовательный метод доступа

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

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

При добавлении новой записи выполняется один из двух алгоритмов:

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

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

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

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

Эффективность доступа при этом методе очень высока, так как индекс содержит ссылки на сами записи, а не на блоки. Но индексные файлы по этой же причине имеют очень большой объем.

Инвертированный метод доступа

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

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

Прямой метод доступа

При этом методе между ключом записи и ее физическим адресом устанавливается взаимно-однозначное соответствие.

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

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

Доступ через хеширование

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

Записи, отображаемые в один адрес называются синонимами.

Алгоритм отображения ключа в физический адрес называется хешированием.

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

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

Смысл их ясен из приведенной таблицы. Следует заметить, что унифицированных расширений имен, принятых в различных ОС, очень мало – по -видимому, только .txt (текст) и расширения для исходных кодов на языках программирования, например, .c – Си , .p или . pas – Паскаль и др. Объектные модули называются по -разному (в Windows – .obj, в UNIX - .o ), библиотеки – тоже: статически линкуемые в Windows - .lib, в UNIX - .a ; динамически линкуемые в Windows - .dll, в UNIX – .so.Интересно отметить, что для исполняемого кода в Windows есть стандартное расширение - .exe,а в UNIX – нет, зато есть весьма экзотическое полное стандартное имя: a.out (assembler output).Унифицированы расширения имен для различных текстовых процессоров: . doc - Microsoft Word , .pdf – Adobe Acrobat и др.

Методы доступа к файлам

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

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

По -видимому, последовательный доступ используется чаще: именно так происходит ввод данных, вывод результатов на печать или на экран.

Методы доступа к файлам

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

Существуют следующие основные типы организации файлов.

Неупорядоченная организация файла предусматривает произвольное неупорядоченное размещение записей на диске.
Упорядоченная (последовательная) организация предполагает размещение записей в соответствии со значением указанного поля.
В хэшированием файле записи хранятся в соответствии со значением некоторой хэш-функции.

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

Метод доступа - действия, выполняемые при сохранении или извлечении записей из файла.

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

Неупорядоченные файлы

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

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

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

Упорядоченные файлы

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

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

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

Таким образом, вставка записи в начало большого файла может оказаться очень длительной процедурой. Для решения этой проблемы часто используется временный неотсортированный файл, который называется файлом переполнения (overflow file) или файлом транзакции (transaction file). При этом все операции вставки выполняются в файле переполнения, содержимое которого периодически объединяется с основным отсортированным файлом. Следовательно, операции вставки выполняются более эффективно, но выполнение операций извлечения данных немного замедляется. Если запись не найдена во время бинарного поиска в отсортированном файле, то приходится выполнять линейный поиск в файле переполнения. И наоборот, при удалении записи необходимо реорганизовать файл, чтобы удалить пустующие места.

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

Знаете ли Вы, в чем фокус эксперимента Майкельсона? Эксперимент А. Майкельсона, Майкельсона - Морли - действительно является цирковым фокусом, загипнотизировавшим физиков на 120 лет.

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

В эксперименте Майкельсона ставится вопрос о движении эфира относительно покоящегося в лабораторной системе интерферометра. Однако, если мы ищем эфир, как базовую материю, из которой состоит всё вещество интерферометра, лаборатории, да и Земли в целом, то, естественно, эфир тоже будет неподвижен, так как земное вещество есть всего навсего определенным образом структурированный эфир, и никак не может двигаться относительно самого себя.

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

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

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

Из этого руководства по операционной системе вы узнаете:

Цель системы управления файлами

Вот основные цели системы управления файлами:

Он обеспечивает поддержку ввода-вывода для различных типов устройств хранения.
Минимизирует шансы потерянных или уничтоженных данных
Помогает ОС стандартизировать подпрограммы интерфейса ввода / вывода для пользовательских процессов.
Он обеспечивает поддержку ввода / вывода для нескольких пользователей в многопользовательской системной среде.

Свойства файловой системы

Вот важные свойства файловой системы:

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

Файловая структура

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

Три типа структуры файлов в ОС:

Текстовый файл: это последовательность символов, организованная в виде строк.
Объектный файл: это серия байтов, которая организована в блоки.
Исходный файл: это набор функций и процессов.

Атрибуты файла

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

Вот некоторые важные атрибуты файла, используемые в ОС:

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

Тип файла

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

Специальный символьный файл

Это аппаратный файл, который читает или записывает данные символьно, например, мышь, принтер и т. Д.

Обычные файлы

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

Файлы каталогов

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

Специальные файлы

Эти файлы также называются файлами устройств. Он представляет физические устройства, такие как принтеры, диски, сети, флэш-накопители и т. Д.

Функции файла

Создайте файл, найдите место на диске и сделайте запись в каталоге.
Запись в файл, требуется позиционирование в файле
Чтение из файла предполагает размещение в файле
Удалить запись каталога, восстановить дисковое пространство.
Перестановка: переместить положение чтения / записи.

Обычно используемые термины в файловых системах

Этот элемент хранит одно значение, которое может быть статическим или переменной длины.

БАЗА ДАННЫХ:

Сбор связанных данных называется базой данных. Отношения между элементами данных являются явными.

RECORD:

Методы доступа к файлам

Три метода доступа к файлам:

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

Последовательный доступ

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

Произвольный доступ

Метод произвольного доступа также называется прямым произвольным доступом. Этот метод позволяет получить доступ к записи напрямую. Каждая запись имеет свой собственный адрес, по которому можно напрямую получить доступ для чтения и записи.

Последовательный доступ

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

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

В операционной системе файлам всегда выделяется дисковое пространство.

Три типа методов выделения пространства:

Связанное распределение
Индексированное распределение
Смежное Распределение

Смежное Распределение

Каждый файл использует непрерывное адресное пространство в памяти.
Здесь ОС назначает адрес диска в линейном порядке.
В методе смежного размещения внешняя фрагментация является самой большой проблемой.

Связанное распределение

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

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

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

Файловые каталоги

Один каталог может содержать или не содержать несколько файлов. Он также может иметь подкаталоги внутри основного каталога. Информация о файлах поддерживается каталогами. В ОС Windows это называется папками.

Читайте также: