2.3.3. Организация файлов на основе таблиц размещения

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

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

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

Рис. 2.4.

Рис.2.5.

2.3.4. Размещение с использованием таблицы индексов

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

Рис.2.6.

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

Главный недостаток этой схемы состоит в том, что добавление и удаление блока файла вызывает изменение всего блока индексов.