4.1.4. Схемы организации данных на внешних носителях

 

Схема адресации записей в файле является определяющей для способов раз­мещения записей в файлах, т.е. условий и процедур включения в файл новых записей, обновления и удаления старых.

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

Для иллюстрации взаимосвязи схем адресации и организации наборов данных рассмотрим процедуру ведения массива индексно-последовательной организации

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

Для работы с индексно-последовательным файлом можно использо­вать два режима обработки: 1) последовательную обработку, при кото­рой записи обрабатываются в последовательности их размещения на внешнем запоминающем устройстве, и 2) произвольную обработку, при которой записи обрабатываются в произвольной последовательно­сти, не связанной с физической организацией записей на внешнем уст­ройстве.

На рис. 4.4 приведена схема индексно-последовательного файла, в который добавлены 3 новые записи.

 

 

Рис. 4.4. Схема индексно-последовательного файла после добавления записей

 

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

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

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

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

 

Методы включения записей, основанные на резервировании

 

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

Наличие некоторого объема свободной памяти в каждом управ­ляемом интервале приводит к тому, что большая часть вновь поступаю­щих записей умещается в пределах соответствующих интервалов. Тем не менее, неизбежны случаи нехватки распределенной свободной памя­ти в интервалах для включения новых записей. В таких случаях осу­ществляется «расщепление» интервала. Предположим, что необходимо включить запись с некоторым значением ключевого поля. В соответст­вии со значением ключевого поля определяется интер­вал, в который следует включить запись. Но, так как интервал уже полностью за­полнен, поэтому осуществляется его расщепление: половина его записей пересылается в свободный ин­тервал, входящий в состав той же управляемой области.

 

Резюмируя, перечислим способы включения в файл новых записей:

1.    При включении новых за­писей файл перезаписывается с размещением записей в соответствующих местах.

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

3.    Записи размещаются в распределенной свободной памяти, которая резервируется при создании базы на уровне физических или логических областей в пространстве файла. При переполнении первоначально зарезервированной области происводится ее расщепление.

 

 

К оглавлению

Назад к разделу "4.1.3. Способы адресации и методы доступа к записям"

Вперед к разделу "4.2. Физическое представление иерархических структур"