Инвертированные индексы
Факт, что в документальных БД поиск обычно проводится по многим ключам доступа, означает, что с точки зрения системы хранение записей в последовательности, определенной единичным ключом доступа, непрактично. Вообще на процессы поиска и выдачи последовательность записей в файле не оказывает большого влияния. Определенная последовательность может быть важна для пользователя только при выводе (например, выданные записи должны быть выведены в алфавитном порядке по автору). Это делается функцией сортировки при генерировании выдачи или отчета.
Программное обеспечение для документальных БД обычно содержит записи в том порядке, в котором они добавляются в файл. Таким образом, пополнение файла происходит по мере добавления новых записей в конец файла. Такой файл называется последовательным, или линейным.
Ниже приводятся две записи из линейного файла библиографической БД:
| AN | |
| TI | The Three Little Pigs |
| AU | Mother Goose |
| PU | Wee Press |
| CY | London |
| PY | |
| AB | Real-life testing of house construction methods Demonstrates advantages and disadvantages of straw, sticks, and bricks |
| DE | Swine, Miniature, Residential Auhitecture |
| ID | Wolf, Big Bad |
| AN | |
| TI | The House That Jack Built |
| AU | Mother Goose PU Children's Book Company Inc. |
| CY | New York |
| PY | |
| AB | Construction tips for novices. Describes occupants of Jack's house. |
| DE | Residential Architecture; Animals in fiction |
| ID | Jack |
Если БД содержит небольшое количество записей, поиск в БД может проводиться путем поочередного перебора значений в каждом поле и в каждой записи во всем массиве линейного файла. Например, чтобы найти записи, содержащие термин „construction", система начнет поиск с номера записи 001. Начиная с первого поля (AN - номер доступа) компьютер будет по очереди перебирать каждый символ, пока не найдет в поле „реферат" (АВ) набор знаков, составляющих слово CONSTRUCTION. Система доложит пользователю, что данная запись содержит искомое слово. В зависимости от используемого программного обеспечения система затем или немедленно выдаст на экран найденную запись, или запомнит ее для выдачи всего списка найденных записей после окончания поиска, а пока продолжит последовательный поиск в линейном файле. Как видно, такой подход несколько непрактичен. Использование логических комбинаций (например, CONSTRUCTION and TESTING) еще более увеличит временные затраты на поиск.
Для ускорения процесса выдачи и предоставления более обширных поисковых функций практически все информационно-поисковые системы сегодня используют инвертированную индексацию. Инвертированные индексы (также называемые словарными файлами) представляют собой список выбранных из линейного файла поисковых слов или фраз, помещенный в отдельный, организованный в алфавитном порядке файл, со ссылками на определенную часть записи в линейном файле. Ниже приводится пример инвертированного файла, который поддерживает доступ к отдельным элементам данных.
| ЭЛЕМЕНТ» | ЗАПИСЬ | ПОЛЕ | ПОЗИЦИЯ ДАННЫХ |
| PV | |||
| РУ | |||
| advantages | ab | ||
| animals | dc | ||
| animals in fiction | dc | 03-05 | |
| architecture | dc | ||
| dc | |||
| bad | id | ||
| big | id | ||
| bricks | ab | ||
| built | ti | ||
| construction | ab | ||
| ab |