Структуры данных и алгоритмы (1021739), страница 85
Текст из файла (страница 85)
Сначала мы покажем, как можно выполнить слияние с шестью буферами (по три на каждый файл), а затем покажем, что будет достаточно четырех буферов, если они будут использоваться совместно для двух файлов.Схема с шестью входными буферамиСхема работы с шестью входными буферами представлена на рис. 11.2 (два выходных буфера здесь не показаны). Для каждого файла предусмотрены три буфера.Каждый буфер рассчитан на Ъ записей.
Заштрихованная область представляетимеющиеся записи, ключи расположены по окружности (по часовой стрелке) в возрастающем порядке. В любой момент времени общее количество невыбранных записей равняется 46 (если только не рассматриваются записи, оставшиеся от объединяемых серий). Поначалу мы считываем в буферы первые два блока из каждой серии.2Поскольку у нас всегда имеется 46 записей, а из одного файла может быть не более36 записей, мы знаем, что имеется по крайней мере Ь записей из каждого файла. Если hi и &2 — наибольшие имеющиеся ключи в двух данных сериях, должно быть 6записей с ключами, не большими, чем klt и 6 записей с ключами, не большими, чемft2.
Таким образом, имеются 6 записей с ключами, не большими, чем min(A1, ft2).1Напрашивается следующее предположение: если действия 1 и 2 занимают одинаковоевремя, значит, операция выбора никогда не пересечется со считыванием. Если целый блок ещене прочитан, можно было бы выбирать среди первых записей этого блока — тех, которыесодержат меньшие ключи. Однако природа считывания с дисков такова, что должно пройтидостаточно длительное время, прежде чем будет найден нужный блок и хотя бы что-нибудьсчитано из него. Таким образом, единственное, о чем можно говорить с уверенностью, этото, что на определенной стадии считывания никакие данные из считываемого блока не доступны для выбора.Если это не первые серии из каждого файла, тогда такую инициализацию можно сделатьпосле того, как будут считаны предыдущие серии и выполнится объединение последних 46 записей из этих серий.320ГЛАВА 11. СТРУКТУРЫ ДАННЫХ И АЛГОРИТМЫ ДЛЯ ВНЕШНЕЙ ПАМЯТИБуферы для файла 1Буферы для файла 2Рис.
11.2. Схема слияния с шестью входными буферамиВопрос о том, какой файл считывать следующим, тривиален. Как правило,поскольку два буфера будут заполнены частично (как показано на рис. 11.2), внашем распоряжении будет только один пустой буфер, который и следует заполнять. Если получается, что каждая серия имеет два полностью заполненных иодин пустой буфер, используйте для заполнения любой из двух пустых буферов.Обратите внимание: наше утверждение о том, что мы не можем исчерпать серию(имеются Ъ записей с ключами, не большими, чем min(fe b k2)), опирается исключительно на факт наличия 46 записей.Стрелки на рис.
11.2 изображают указатели на первые (с наименьшими ключами)имеющиеся записи из двух данных серий. В языке Pascal можно представить такойуказатель в виде двух целых чисел. Первый, в диапазоне 1-3, представляет"указываемый" буфер, а второй, в диапазоне 1-Ь, — запись в этом, буфере. Как альтернативный вариант мы могли бы реализовать эти буферы в виде первой, средней ипоследней трети одного массива и использовать одно целое число в диапазоне 1-36.При использовании других языков, в которых указатели могут указывать на элементы массивов, следует предпочесть указатель типа Trecordtype.Схема с четырьмя буферамиНа рис.
11.3 представлена схема с четырьмя буферами. В начале каждогоэтапа у нас имеется 26 записей. Два входных буфера назначаются одному изфайлов (Bj и Б2 на рис. 11.3 назначены файлу 1). Один из этих буферов будетзаполнен частично (в крайнем случае он будет пустым), а другой — полностью.Третий буфер назначается другому файлу, например В3 на рис. 11.3 назначенфайлу 2. Он заполнен частично (в крайнем случае он будет заполнен полностью).Четвертый буфер не назначается ни одному из файлов. На данной стадии он заполняется из одного из этих файлов.Мы, конечно, сохраняем возможность выполнения слияния параллельно со считыванием: по крайней мере Ъ записей из тех, которые показаны на рис. 11.3, должны иметь ключи, не превышающие min(&i, k^), где k\ и k2 — ключи последнихимеющихся записей из двух данных файлов.
Конфигурацию буферов, которая позволяет выполнять параллельную работу по слиянию и считыванию, назовем безопасной. Поначалу считывается один блок из каждого файла (крайний случай, когда буфер BI пустой, а буфер Б3 целиком заполнен); в результате начальная конфигурацияоказывается безопасной. Мы должны (в предположении, что ситуация, представленная на рис. 11.3, соответствует безопасной конфигурации) показать, что конфигурация будет безопасной и после завершения следующего этапа.11.2. ВНЕШНЯЯ СОРТИРОВКА321Если ki < k2, тогда надо заполнить В4 следующим блоком из файла 1; в противном случае заполняем его из файла 2.
Допустим сначала, что ftt < k2. Поскольку буферы BI и Б3 на рис. 11.3 содержат в точности Ъ записей, на следующем этапе мыдолжны исчерпать BI; в противном случае мы исчерпали бы В3 и нарушили безопасность конфигурации, представленной на рис. 11.3. Таким образом, по завершенииэтапа конфигурация примет вид, показанный на рис.
11.4,а./с2В,Буферыдля файла 1Буфердля файла 2Рис. 11.3. Схема слияния с четырьмя буферамиЧтобы убедиться в том, что конфигурация на рис. 11.4,а действительно безопасна, рассмотрим два случая. Во-первых, если k3 (последний ключ во вновь прочитанном блоке В4) оказывается меньше k2, тогда при целиком заполненном блоке Б4можно быть уверенным в наличии Ъ записей, не превышающих min(fti, A2), поэтомусоответствующая конфигурация является безопасной. Если &2 ^ *з. тогда в силупредположения, что ki < k2 (в противном случае мы заполнили бы В4 из файла 2), Ьзаписей в Б2 и В3 имеют ключи, не превышающие min(fc2. &з) ~ k2.Теперь рассмотрим случай, когда fei > k2 (см. рис.
11.3). Здесь необходимо считывать следующий блок из файла 2. На рис. 11.4,6 показана итоговая ситуация. Как ив случае ki < k2, можно утверждать, что Вг должен исчерпаться, вот почему нарис. 11.4,6 показано, что файл 1 имеет только буфер Б2. Доказательство того, что нарис. 11.4,6 показана безопасная конфигурация, ничем не отличается от доказательства подобного факта для рис. 11.4,а.Обратите внимание: как и в случае схемы с шестью входными буферами, мы несчитываем файл после конца серии. Но если нет необходимости считывать блок изодной из имеющихся серий, мы может считать блок из следующей серии в том жефайле. Таким образом, у нас появляется возможность считать один блок из каждойиз следующих серий и приступить к слиянию серий сразу же после того, как будутвыбраны последние записи предыдущей серии.322ГЛАВА 11.
СТРУКТУРЫ ДАННЫХ И АЛГОРИТМЫ ДЛЯ ВНЕШНЕЙ ПАМЯТИS2БуферыБуфердля файла 1 для файла 2БуферБуферыдля файла 1 для файла 2аРис. 11.4. Конфигурация буферов по завершении одного этапа11.3. Хранение данных в файлахВ этом разделе мы рассмотрим структуры данных и алгоритмы для хранения ипоиска информации в файлах, находящихся во внешней памяти. Файл мы будемрассматривать как последовательность записей, причем каждая запись состоит изодной и той же совокупности полей. Поля могут иметь либо фиксированную длину(заранее определенное количество байт), либо переменную. Файлы с записями фиксированной длины широко используются в системах управления базами данных дляхранения данных со сложной структурой. Файлы с записями переменной длины, какправило, используются для хранения текстовой информации; в языке Pascal такиефайлы не предусмотрены.
В этом разделе будем иметь дело с полями фиксированнойдлины; рассмотренные методы работы после определенной (несложной) модификациимогут использоваться для работы с записями переменной длины.Мы рассмотрим следующие операторы для работы с файлами.1.2.3.4.INSERT вставляет определенную запись в определенный файл.DELETE удаляет из определенного файла все записи, содержащие указанныезначения в указанных полях.MODIFY изменяет все записи в определенном файле, задав указанные значенияопределенным полям в тех записях, которые содержат указанные значения вдругих полях.RETRIEVE отыскивает все записи, содержащие указанные значения в указанных полях.11.3. ХРАНЕНИЕ ДАННЫХ В ФАЙЛАХ323Пример 11.3.
Допустим, например, что есть файл, записи которого состоят изтрех полей: фамилия, адрес и телефон. Нам может понадобиться отыскать всезаписи, у которых телефон = "555-1234", вставить запись ("Петя Иванов", "ул.8-го марта, 12", "555-1234") или удалить все записи с фамилия — "Петя Иванов"и адрес = "ул. 8-го марта, 12". Или, например, нам может понадобиться изменить все записи, у которых фамилия — "Петя Иванов", установив для поля телефон значение "555-1234".
ПРассматривая операции с файлами, в первом приближении можно считать, чтофайлы — это просто совокупности записей, над которыми можно выполнять операторы, обсуждавшиеся в главах 4 и 5. Однако имеются два важных отличия. Вопервых, когда мы говорим о файлах, хранящихся на устройствах внешней памяти,то при оценивании тех или иных стратегий организации файлов нужно использовать меру затрат, обсуждавшихся в разделе 11.1. Другими словами, мы предполагаем, что файлы хранятся в виде некоторого количества физических блоков, а затраты на выполнение оператора пропорциональны количеству блоков, которые мыдолжны считать в основную память или записать из основной памяти на устройство внешней памяти.Второе отличие заключается в том, что для записей, представляющих собой конкретные типы данных в большинстве языков программирования, могут быть предусмотрены указатели, в то время как для абстрактных элементов из некоторой совокупности никакие "указатели" предусмотреть нельзя.
Например, в системах баз данных при организации данных часто используются указатели на записи. Следствиемприменения подобных указателей является то, что записи часто приходится считатьзакрепленными: их нельзя перемещать во внешней памяти, поскольку не исключено,что какой-то неизвестный нам указатель после таких перемещений записи будет указывать неправильный адрес этой записи.Простой способ представления указателей на записи заключается в следующем. Укаждого блока есть определенный физический адрес, т.е. место начала этого блока наустройстве внешней памяти.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
