Индексно-последовательные файлы

Индексно-последовательные файлы допускают как последовательный, так и прямой доступы к блокам. При этом могут быть использованы такие же возможности, которые характерны для последовательных файлов и файлов прямого доступа. Это значит, что в индексно-последовательном файле можно последовательно читать или записывать блоки, по желанию обращаться к любому отдельному блоку с целью его чтения или модификации, а также вставлять новый блок в любое место файла, определяемое значением ключа блока. Индексно-последовательный файл создается только на ЗУПД. Каждый блок такого блока непременно должен иметь уникальный ключ, который используется для идентификации блока, а также для логического упорядочения блоков в файле. Если блок содержит несколько логических записей, то ключом всего блока является ключ последней логической записи в блоке, который имеет максимальное значение, поскольку логические записи в блоке упорядочены по ключу.

Все пространство внешней памяти на ЗУПД, выделенное для индексно-последовательного файла, состоит из трех функционально различных областей: основной области, области переполнения и индексной области, или области индексов.

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

При первоначальной загрузке индексно-последовательный файл организуется как последовательный файл, блоки которого логически и физически упорядочены по ключу в основной области. Предполагается, что блоки загружаются в файл строго в порядке возрастания ключей. Область переполнения при первоначальной загрузке файла не используется и остается пустой.

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

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

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

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

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

 


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

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

Дата: 2019-02-19, просмотров: 25.