Главная Промышленная автоматика.

Пример П.З. Допустим, например, что есть файл, записи которого состоят из трех полей: фамилия, адрес и телефон. Нам может понадобиться отыскать все записи, у которых телефон = "555-1234", вставить запись ("Петя Иванов", "ул. 8-го марта, 12", "555-1234") или удалить все записи с фамилия - "Петя Иванов" и адрес = "ул. 8-го марта, 12". Или, например, нам может понадобиться изменить все записи, у которых фамилия - "Петя Иванов", установив для поля телефон значение "555-1234". □

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

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

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

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

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

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



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

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

2. Предусмотреть для каждой записи специальный бит удаления; этот бит содержит 1 в удаленных записях и О - в "настоящих" записях.

Ускорение операций с файлами

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

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

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

Хешированные файлы

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



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

Такой способ организации показан на рис. И.5. Основное различие мевду рис. 11.5 и 4.3 заключается в том, что в данном случае элементы, хранящиеся в одном блоке сегмента, не требуется связывать друг с другом с помошью указателей - связывать мевду собой нужно только блоки.


Г- л fi

1 2 Э

Таблица сегментов

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

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

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

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

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





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 [104] 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.002