Структуры данных и алгоритмы (1021739), страница 86
Текст из файла (страница 86)
Отслеживание физических адресов является задачейфайловой системы. Одним из способов представления адресов записей является использование физического адреса блока, содержащего интересующую нас запись, сосмещением, указывающим количество байт в блоке, предшествующих началу этойзаписи. Такие пары "физический адрес-смещение" можно хранить в полях типа"указатель на запись".Простая организация данныхПростейшим (и наименее эффективным) способом реализации перечисленныхвыше операторов работы с файлами является использование таких примитивов чтения и записи файлов, которые встречаются, например, в языке Pascal. В случае использования подобной "организации" (которая на самом деле является дезорганизацией) записи могут храниться в любом порядке.
Поиск записи с указанными значениями в определенных полях осуществляется путем полного просмотра файла ипроверки каждой его записи на наличие в ней заданных значений. Вставку в файлможно выполнять путем присоединения соответствующей записи к концу файла.В случае изменения записей необходимо просмотреть файл, проверить каждуюзапись и выяснить, соответствует ли она заданным условиям (значениям в указанных полях). Если соответствует, в запись вносятся требуемые изменения. Принципдействия операции удаления почти тот же, но когда мы находим запись, поля которой соответствуют значениям, заданным в операции удаления, мы должны найтиспособ удалить ее. Один из вариантов — сдвинуть все последовательные записи всвоих блоках на одну позицию вперед, а первую запись в каждом последующем блоке переместить на последнюю позицию предыдущего блока данного файла. Однакотакой подход не годится, если записи являются закрепленными, поскольку указатель на i-ю запись в файле после выполнения этой операции будет указывать на(i + 1)-к> запись.324ГЛАВА 11.
СТРУКТУРЫ ДАННЫХ И АЛГОРИТМЫ ДЛЯ ВНЕШНЕЙ ПАМЯТИЕсли записи являются закрепленными, нам следует воспользоваться каким-тодругим подходом. Мы должны как-то помечать удаленные записи, но не .должнысмещать оставшиеся на место удаленных (и не должны вставлять на их место новыезаписи). Таким образом выполняется логическое удаление записи из файла, но ее место в файле остается незанятым. Это нужно для того, чтобы в случае появления указателя на удаленную запись мы могли, во-первых, понять, что указываемая записьуже удалена, и, во-вторых, предпринять соответствующие меры (например, присвоить этому указателю значение NIL, чтобы в следующий раз не тратить время на егоанализ). Существуют два способа помечать удаленные записи.1.2.Заменить запись на какое-то значение, которое никогда не может стать значением "настоящей" записи, и, встретив указатель на какую-либо запись, считать ееудаленной, если она содержит это значение.Предусмотреть для каждой записи специальный бит удаления; этот бит содержит 1 в удаленных записях и 0 — в "настоящих" записях.Ускорение операций с файламиОчевидным недостатком последовательного файла является то, что операторы стакими файлами выполняются медленно.
Выполнение каждой операции требует,чтобы мы прочитали весь файл, а после этого еще и выполнили перезапись некоторых блоков. К счастью, существуют такие способы организации файлов, которые позволяют нам обращаться к записи, считывая в основную память лишь небольшуючасть файла.Такие способы организации файлов предусматривают наличие у каждой записифайла так называемого ключа, т.е. совокупности полей, которая уникальным образомидентифицирует каждую запись. Например, в файле с полями фамилия, адрес, телефон, поле фамилия само по себе может считаться ключом, т.е.
мы можем предположить, что в таком файле не может одновременно быть двух записей с одинаковым значением поля фамилия. Поиск записи, когда заданы значения ее ключевых полей, является типичной операцией, на обеспечение максимальной эффективности которойориентированы многие широко распространенные способы организации файлов.Еще одним непременным атрибутом быстрого выполнения операций с файламиявляется возможность непосредственного доступа к блокам (в отличие от последовательного перебора всех блоков, содержащих файл). Многие структуры данных, которые мы используем для быстрого выполнения операций с файлами, используют указатели на сами блоки, которые представляют собой физические адреса этих блоков (офизических адресах блоков было сказано выше).
К сожалению, на языке Pascal (имногих других языках программирования) невозможно писать программы, работающие с данными на уровне физических блоков и их адресов, — такие операции, какправило, выполняются с помощью команд файловой системы. Однако мы приведемкраткое неформальное описание принципа действия операторов, в которых используется прямой доступ к блокам.Хешированные файлыХеширование — широко распространенный метод обеспечения быстрого доступа кинформации, хранящейся во вторичной памяти.
Основная идея этого метода подобнаоткрытому хешированию, которое мы обсуждали в разделе 4.7. Записи файла мыраспределяем между так называемыми сегментами, каждый из которых состоит изсвязного списка одного или нескольких блоков внешней памяти. Такая организацияподобна той, которая была представлена на рис. 4.3. Имеется таблица сегментов, содержащая В указателей, — по одному на каждый сегмент. Каждый указатель в табглице сегментов представляет собой физический адрес первого блока связного спискаблоков для соответствующего сегмента.11.Зи ХРАНЕНИЕ ДАННЫХ В ФАЙЛАХ325Сегменты пронумерованы от 0 до В-1.
Хеш-функция А отображает каждое значение ключа в одно из целых чисел от 0 до В-1. Если х — ключ, то h(x) является номером сегмента, который содержит запись с ключом х (если такая запись вообщесуществует). Блоки, составляющие каждый сегмент, образуют связный список. Таким образом, заголовок i-ro блока содержит указатель на физический адрес (i + 1)-гоблока. Последний блок сегмента содержит в своем заголовке NIL-указатель.Такой способ организации показан на рис. 11.5.
Основное различие междурис. 11.5 и 4.3 заключается в том, что в данном случае элементы, хранящиеся в одном блоке сегмента, не требуется связывать друг с другом с помощью указателей —связывать между собой нужно только блоки.г7 гв•ТаблицасегментовРис. 11.5. Сегменты, состоящие из связанных блоковЕсли размер таблицы сегментов невелик, ее можно хранить в основной памяти.
Впротивном случае ее можно хранить последовательным способом в отдельных блоках.Если нужно найти запись с ключом х, вычисляется h(x) и находится блок таблицысегментов, содержащий указатель на первый блок сегмента h(x). Затем последовательно считываются блоки сегмента h(x), пока не обнаружится блок, который содержит запись с ключом х. Если исчерпаны все блоки в связном списке для сегментаh(x), приходим к выводу, что х не является ключом ни одной из записей.Такая структура оказывается вполне эффективной, если в выполняемом операторе указываются значения ключевых полей.
Среднее количество обращений к блокам,требующееся для выполнения оператора, в котором указан ключ записи, приблизительно равняется среднему количеству блоков в сегменте, которое равно n/bk, еслип — количество записей, блок содержит Ь записей, a k соответствует количеству сегментов.
Таким образом, при такой организации данных операторы, использующиезначения ключей, выполняются в среднем в k раз быстрее, чем в случае неорганизованного файла. К сожалению, ускорения операций, не основанных на использованииключей, добиться не удается, поскольку при выполнении подобных операций намприходится анализировать практически все содержимое сегментов. Единственнымуниверсальным способом ускорения операций, не основанных на использованииключей, по-видимому, является применение вторичных индексов, о которых мы поговорим в конце этого раздела.Чтобы вставить запись с ключом, значение которого равняется х, нужно сначалапроверить, нет ли в файле записи с таким значением ключа.
Если такая запись есть,выдается сообщение об ошибке, поскольку мы предполагаем, что ключ уникальнымобразом идентифицирует каждую запись. Если записи с ключом х нет, мы вставляемновую запись в первый же блок цепочки для сегмента h(x), в который эту записьудается вставить. Если запись не удается вставить ни в какой из существующихблоков сегмента h(x), файловой системе выдается команда найти новый блок, в который будет помещена эта запись.
Этот новый блок затем добавляется в конец цепочкиблоков сегмента h(x).Чтобы удалить запись с ключом х, нужно сначала найти эту запись, а затем установить ее бит удаления. Еще одной возможной стратегией удаления (которой, впро326ГЛАВА 11. СТРУКТУРЫ ДАННЫХ И АЛГОРИТМЫ ДЛЯ ВНЕШНЕЙ ПАМЯТИчем, нельзя пользоваться, если мы имеем дело с закрепленными записями) являетсязамена удаленной записи на последнюю запись в цепочке блоков сегмента h(x). Еслитакое изъятие последней записи приводит к опустошению последнего блока в сегменте h(x), этот пустой блок можно затем вернуть файловой системе для повторного использования.Хорошо продуманная организация файлов с хешированным доступом требуетлишь незначительного числа обращений к блокам при выполнении каждой операциис файлами.
Если мы имеем дело с хорошей функцией хеширования, а количествосегментов приблизительно равно количеству записей в файле, деленному на количество записей, которые могут уместиться в одном блоке, -тогда средний сегмент состоит из одного блока. Если не учитывать обращения к блокам, которые требуются дляпросмотра таблицы сегментов, типичная операция поиска данных, основанного наключах, потребует лишь одного обращения к блоку, а операции вставки, удаленияили изменения потребуют двух обращений к блокам.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
