В контексте задач поиска можно сказать, что существуют два основных способа организации данных. Первый представляет прямую организацию массива. Второй является инверсией первого. Прямая организация массива удобна для поиска по условия «Каковы свойства указанного объекта?», а инвертированная – для поиска по условию «Какие объекты обладают указанным свойством?». Типология простых (атомарных) запросов: 1) А(Е)=? – каково значение атрибута а для объекта Е 2) А(?)=V – Какие объекты имеют значение атрибута, равное V 3) ?(E)=V – какие атрибуты объекта Е имеют значение, равное V 4) ?(E)=? – какие значения атрибутов имеет объект Е? 5) А(?)=? Какие значения имеет атрибут А в наборе? 6) ?(?)=V – какие атрибуты объектов набора имеют значение, равное V? Здесь в запросах типов 2,3,6 вместо оператора равенства может быть использован другой оператор сравнения (больше, меньше, е равно или другие). Запросы типа 1 выполняются поиском по «прямому» массиву: доступ к записи производится по первичному ключу. Запросы типа 2 выполняются поиском по инвертированному списку: доступ к записи(ям) производится по указателю, выбираемому из списка по значению вторичного ключа. Ответом в этих случаях будет значение атрибута или идентификатора. Запросы типа 3 имеют ответом имя атрибута. Запросы типа 2,5,6 относятся к нескольким атрибутам, и в этом случае могут быть построены несколько индексов, облегчающих поиск по этим ключам. Составные условия поиска могут использовать несколько простых условий, обычно связанных логическими (булевыми) операторами. Следует отметить, что в контексте обработки запросов 2-го типа «Какие объекты имеют значение атрибута?» можно выделить три следующих типа архитектур доступа. 1. Системы с вторичными индексами. В этих системах последовательность расположения записей соответствует последовательности значений первичного ключа. Как правило, используется один первичный индекс и несколько вторичных. 2. Системы частично инвертированных файлов. В этих системах записи могут располагаться в произвольной последовательности. В отличие от систем первого типа первичный индекс отсутствует. Вторичные индексы применяются для прямой адресации записей, что существенно облегчает включение в файл новых записей, так как допускается их размещение в любом свободном участке файла. 3. Системы полностью инвертированных файлов. В этих системах предусмотрено наличие файлов, содержащих значения отдельных элементов данных, входящих в состав записей, - допускается раздельное хранение элементов данных записи. Значения элементов данных, оставляющих конкретную запись или кортеж, в общем случае могут размещаться в памяти произвольно. Для ускорения процесса поиска в системе используют два набора индексов: индекс экземпляров (значений ключей) и индекс данных (инвертированный список). С помощью индекса экземпляров можно найти в файле элементы данных, имеющих заданное значение. С помощью индекса данных можно найти записи, связанные с заданными значениями элементов. Акая организация характерна для организации данных документальных информационных систем.
