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






Буферы для файла 1 Буферы для файла 2

Рис. 11.2, Схема слияния с шестью входными буферами

Вопрос о том, какой файл считывать следуюшим, тривиален. Как правило, поскольку два буфера будут заполнены частично (как показано на рис. 11.2), в нашем распоряжении будет только один пустой буфер, который и следует заполнять. Если получается, что каждая серия имеет два полностью заполненных и один пустой буфер, используйте для заполнения любой из двух пустых буферов. Обратите внимание: наше утвервдение о том, что мы не можем исчерпать серию (имеются Ъ записей с ключами, не большими, чем min(Ai, /гг)), опирается исключительно на факт наличия 46 записей.

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

Схема с четырьмя буферами

На рис. 11.3 представлена схема с четырьмя буферами. В начале каждого этапа у нас имеется 26 записей. Два входных буфера назначаются одному из файлов (Bi и Вг на рис. 11.3 назначены файлу 1). Один из этих буферов будет заполнен частично (в крайнем случае он будет пустым), а другой - полностью. Третий буфер назначается другому файлу, например Вз на рис. 11.3 назначен файлу 2. Он заполнен частично (в крайнем случае он будет заполнен полностью). Четвертый буфер не назначается ни одному из файлов. На данной стадии он заполняется из одного из этих файлов.

Мы, конечно, сохраняем возможность выполнения слияния параллельно со считыванием: по крайней мере Ъ записей из тех, которые показаны на рис. 11.3, должны иметь ключи, не превышаюшие min(/Ji, Аг). где ki я kz - ключи последних имеющихся записей из двух данных файлов. Конфигурацию буферов, которая позволяет выполнять параллельную работу по слиянию и считыванию, назовем безопасной. Поначалу считывается один блок из кавдого файла (крайний случай, когда буфер Bj пустой, а буфер Bj целиком заполнен); в результате начальная конфигурация оказывается безопасной. Мы должны (в предположении, что ситуация, представленная на рис. 11.3, соответствует безопасной конфигурации) показать, что конфигурация будет безопасной и после завершения следуюшего этапа.



Если ki < кг, тогда надо заполнить В4 следующим блоком из файла 1; в противном случае заполняем его из файла 2. Допустим сначала, что ft, < 2- Поскольку буферы Bi и Вз на рис. И.З содержат в точности Ъ записей, на следующем этапе мы должны исчерпать Bi; в противном случае мы исчерпали бы Bj и нарушили безопасность конфигурации, представленной на рис. И.З. Таким образом, по завершении этапа конфигурация примет вид, показанный на рис. 11.4,а.


Буферы для файла 1

Буфер для файла 2

Рис. 11.3. Схема слияния с четырьмя буферами

Чтобы убедиться в том, что конфигурация на рис. 11.4,а действительно безопасна, рассмотрим два случая. Во-первых, если к (последний ключ во вновь прочитанном блоке в4) оказывается меньше kz, тогда при целиком заполненном блоке В4 можно быть уверенным в наличии Ъ записей, не превышающих niin(fti, /Jj), поэтому соответствующая конфигурация является безопасной. Если ftj тогда в силу предположения, что ft, < (в противном слзчае мы заполнили бы В4 из файла 2), Ь записей в Вз и Вз имеют ключи, не превышающие min(A2. *з) ~ 2-

Теперь рассмотрим случай, когда fei > (см. рис. И.З). Здесь необходимо считывать следующий блок из файла 2. На рис. 11.4,6 показана итоговая ситуация. Как и в случае ку < к, можно утверждать, что В, должен исчерпаться, вот почему на рис. 11.4,6 показано, что файл 1 имеет только буфер Bj. Доказательство того, что на рис. 11.4,6 показана безопасная конфигурация, ничем не отличается от доказательства подобного факта для рис. 11.4,а.

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





Буферы Буфер

для файла 1 для файла 2

Буфер Буферы

для файла 1 для файла 2

Рис. 11.4. Конфигурация буферов по завершении одного этапа

11.3. Хранение данных в файлах

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

Мы рассмотрим следуюшие операторы для работы с файлами.

1. 2.

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

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

значения в указанных полях.

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

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





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.0018