Индексированные файлы

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

Пример 1. На рис.3 показан файл, а так же соответствующий ему файл разреженного индекса.

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

Рис.3. Основной файл и его разреженный индекс.

Чтобы отыскать запись с заданным ключом х, надо сначала просмотреть индексный файл, отыскивая в нем пару (x, b). В действительности отыскивается наибольшее z, такое, что z   x и далее находится пара (z, b). В этом случае ключ х оказывается в блоке b (если такой ключ вообще присутствует в данном файле).

Разработано несколько стратегий просмотра индексного файла. Простейшим из них является линейный поиск. Индексный файл читается с самого начала, пока не встретится пара (x, b) или (y, b), причем у > х. В последнем случае у предыдущей пары (z, b1) должно быть z < x, и если запись с ключом х действительно существует, то она находится в блоке b1.

Линейный поиск годится лишь для небольших индексных файлов. Более эффективным методом является двоичный поиск. Допустим, индексный файл хранится в блоках b1, b2, ..., bn. Чтобы отыскать значение ключа х , берется средний блок b[n/2] и х сравнивается со значением ключа у в первой паре данного блока. Если х < у, но х меньше, чем ключ блока b[n/2]+1, используется линейный поиск, чтобы проверить, совпадает ли х с первым компонентом индексной пары в блоке b[n/2]. В противном случае повторяется поиск в блоках b[n/2]+1, b[n/2]+2, ..., bn. При использовании двоичного поиска нужно проверить лишь [log2(n+1)] блоков индексного файла.

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

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