13. Методы ускорения операций обработки файловых структур данных.

Очевидным недостатком последовательного файла является то, что операторы с такими файлами выполняются медленно.

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

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

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

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

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

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

Однако мы приведем краткое неформальное описание принципа действия операторов, в которых используется прямой доступ к блокам.

Хеширование - широко распространенный метод между так называемыми сегментами, каждый из которых состоит из связного списка одного или нескольких блоков внешней памяти.

Имеется таблица сегментов, содержащая В указателей, - по одному на каждый сегмент.

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

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

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

Чтобы облегчить процедуру поиска, можно создать второй файл, называемый разреженным индексом, который состоит из пар

(х, b),

где х - значение ключа,

а b - физический адрес блока, в котором значение ключа первой записи равняется х.

Этот разреженный индекс отсортирован по значениям ключей.

Более эффективным методом является двоичный поиск.

Допустим, что индексный файл хранится в блоках b₁, b₂, ... , b_n.

Чтобы отыскать значение ключа х, берется средний блок b_[n/2] и х сравнивается со значением ключа у в первой паре данного блока.

Если х < у, поиск повторяется в блоках b₁, b₂, ... , b_[n/2]-1.

Если х  у, но х меньше, чем ключ блока b_[n/2]+1 используется линейный поиск, чтобы проверить, совпадает ли х с первым компонентом индексной пары в блоке b_[n/2].

В противном случае повторяется поиск в блоках b_[n/2]+1, b_[n/2]+2, ... , b_n.

При использовании двоичного поиска нужно проверить лишь [Iog₂(n+1)] блоков индексного файла.

12