Индексные структуры

Требования к индексным структурам:

• время обработки запроса – должно обеспечиваться заданное время обработки запроса, которое должно расти менее чем линейно от роста размера коллекции.
• компактное представление – индексная структура должна занимать минимальный возможный объем на диске, кроме этого обеспечивая и минимальный объем данных, которые потребуется передавать с диска при обработке запроса.
• время изменения – при добавлении, изменении, удалении документов должно обеспечиваться должное время обработки.

Варианты индексных структур, обеспечивающие модель документа на основе входящих в него символов:

• инвертированные файлы – структура состоящая из словаря встречающихся термов и списка документов для каждого, в котором этот терм встречается.
• сигнатурные файлы – каждый документ представлен некоторой сигнатурой, биты которой говорят о наличии или отсутствии в нем определенных термов или групп термов.
• суффиксные деревья – структуры, содержащие ссылки на все возможные подстроки в текстовой коллекции.

Каждая из структур глубоко исследована, но на практике обычно используются инвертированные файлы, которые для большинства задач превосходят остальные структуры по описанным параметрам.