Структуры и алгоритмы обработки данных. Ключарев А.А - 66 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

66
файла в отсортированном (по значению ключа) порядке. Чтобы облегчить
процедуру поиска, можно создать второй файл, называемый разрежен-
ным индексом, который состоит из пар (x, b), где x – значение ключа, а b
– физический адрес блока, в котором значение ключа первой записи равня-
ется x. Этот индексный файл отсортирован по значению ключей.
Индексный файл
3 10 23
28 42
3 5 8 10 11 16 23 25 27 28 31 38 42 46
Рис. 18. Разреженный индекс
Чтобы отыскать запись с заданным ключом x, необходимо сначала
просмотреть индексный файл, отыскивая в нем пару (x, b), а затем на-
ходят запись в блоке с физическим адресом b. Разработано несколько
стратегий просмотра индексного файла. Простейшей из них является
линейный поиск, более эффективным является двоичный поиск. Эти
методы рассматриваются в 2.3.1. Для поиска записи необходимо счи-
тать один блок основного файла, и в зависимости от стратегии про-
смотра индексного файла просмотреть от n (при линейном поиске) до
log
2
(n + 1) (при двоичном поиске) блоков индексного файла, где n –
общее количество блоков индексного файла.
Чтобы создать индексированный файл, записи сортируются по зна-
чениям их ключей, а затем распределяются по блокам в возрастающем
порядке ключей. В каждый блок можно разместить столько записей,
сколько в него помещается, но можно оставить место под записи, кото-
рые могут вставляться туда впоследствии (это уменьшает вероятность
переполнения и, следовательно, обращение к смежным блокам). После
распределения записей по блокам создается индексный файл. В нем
также можно оставить место для новых индексов.
Чтобы вставить новую запись, с помощью индексного файла находят
соответствующий блок основного файла. Если новая запись умещается
в найденный блок, то она вставляется в него в правильной последова-
тельности. Если новая запись становится первой записью в блоке, то
необходима корректировка индексного файла.
Если новая запись не умещается в найденный блок, то возможно
применение нескольких стратегий. Простейшая из них заключается в

Страницы