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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сегменты пронумерованы от 0 до В-1. Хеш-функция h отображает каждое значение ключа в одно из целых чисел от 0 до В-1. Если x – ключ, то h(x) является номером сегмента, который содержит запись с ключом х (если такая запись вообще существует). Блоки, составляющие каждый сегмент, образуют связный список. Таким образом, заголовок i-го блока содержит указатель на физический адрес (i+1)-го блока. Последний блок сегмента содержит в своём заголовке NIL-указатель.

Рис.2. Сегменты, состоящие из связных блоков.

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

Такая структура оказывается вполне эффективной, если в выполняемом операторе указываются значения ключевых полей. Среднее количество обращения к блокам, требующееся для выполнения оператора, в котором указан ключ записи, приблизительно равняется среднему количеству блоков в сегменте, которое равно n/bk, если n – количество записей, блок содержит b записей, а k соответствует количеству сегментов. Таким образом, при такой организации данных операторы, использующие значения ключей, выполняются в среднем в k раз быстрее, чем в случае неорганизованного файла. К сожалению, ускорения операций, не основанных на использовании ключей, добиться не удаётся, поскольку при выполнении подобных операций приходится анализировать практически всё содержимое сегментов. Единственным универсальным способом ускорения операций, не основанных на использовании ключей, по-видимому, является применение вторичных индексов.

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

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

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

ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...

Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...

ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: