Автоматизация геофизических исследований в высоких широтах.

Однако при поиске по двум и более ключам данная схема адресации неэффективна, поэтому для поиска по нескольким ключам используются секционные инвертированные списки, представленные битовыми строками / 1 / . Инвертированный список, это такой, в ко­ тором длина цепи, включающей все элементы файла, изменяется до одного звена. При данном методе адресаций в индексе хранится не точный адрес записи, а номер секции запоминающего устройства, в которой находится искомая запись. В нашем случае секцией запо­ минающего устройства является один цилиндр. Индекс для каждого ключа представляет собой битовую матрицу, в которой каждая стро­ ка соответствует одному из значений заданного ключа. Если запись с каким-либо значением ключа находится в определенной секции, то бит, соответствующий данной секции, возводится в единицу. При­ мер битовой матрицы приведен на рис.2. ш ч і Ключ2. п и и к л ю ч а { 2 3 ч 5 6 7 I 8 9 00/ / 0 0 / 0 1 / 0 0 004 0 / 0 0 / < 0 0 0 002 / / / 0 / / 0 1 / 001 0 0 / / 0 1 0 0 0 003 і 1 0 0 1 0 / / 0 006 < / { 0 0 / 0 / У _______ - — ---- J_____ у- — Рис .2 . Пример битовой матрицы. При поиске по двум и более ключам определяются строки мат­ риц, соответствующие заданным значениям ключей, и над выбран­ ными строками производится операция конъюнкции. В результате требуется просмотреть лишь те секции, которым соответствуют еди­ ничные биты. Таким образом, в системе для адресации файла каталога ис­ пользуются восемь индексов. Размеры каждого индекса по цепям составляют ѵ 1 Килобайта (Кб), а битовая матрица ^ 2 Кб, т.е. размеры индексов сравнительно невелики. В зависимости от з а ­ проса в основную память ЭВМ считывается один, два или более индексов. Поиск в индексе в основной памяти осуществляется после­ довательным сканированием. При пополнении каталога индексы автоматически модифицируют­ ся. На модификацию всех индексов требуется около 2 5 мин.при пополнении каталога на 1 0 0 паспортов. 45