Инвертированный индекс
- title
- Инвертированный индекс
- type
- concept
- summary
- Структура данных, сопоставляющая термы с документами; основа всех систем полнотекстового поиска
- parent
- hybrid-search
- tags
- search, data-structures, information-retrieval
- created
- 2026-04-08
- updated
- 2026-04-08
- lang
- ru
- translation_of
- inverted-index
- source_updated
- 2026-04-08
- translated
- 2026-09-01
- translator
- lllm/antigravity/gemini-3.7-flash-medium
Структура данных, которая сопоставляет термы с документами (или позициями), в которых они встречаются, - в противоположность документу, сопоставляющему термы. По запросу со словом "quantum" инвертированный индекс возвращает список всех документов, где встречается "quantum", обычно с метаданными вроде частоты и позиции.
Любая система полнотекстового поиска построена на той или иной форме инвертированного индекса. Lucene, SQLite FTS, индексы GIN в PostgreSQL и даже индексы multiEntry в indexeddb - всё это вариации одной идеи: заранее вычислить сопоставление термов с документами при записи, чтобы чтение затрагивало только релевантные документы.
Структура
Минимальный инвертированный индекс представляет собой словарь вида терм -> posting list, где каждый posting list - это набор идентификаторов документов, содержащих данный терм. Более продвинутые версии хранят частоту терма (для подсчёта ранга по TF-IDF/BM25), позиции (для фразовых запросов) и информацию о полях (для поиска по нескольким полям).
Построение индекса
При записи: токенизировать документ, при необходимости выполнить стемминг и удалить стоп-слова, затем добавить ID документа в posting list каждого терма. При запросе: найти posting list для каждого терма из запроса, затем пересечь их (для запросов с AND) или объединить (для запросов с OR).
В статье full-text-search-indexeddb показан минимальный вариант с использованием флага multiEntry в IndexedDB - встроенный в браузер механизм B-tree индексов берёт работу с posting list'ами на себя.
Затраты
Инвертированные индексы жертвуют скоростью записи и дисковым пространством ради скорости чтения. Каждая вставка документа обновляет множество posting list'ов. Объём хранимых данных увеличивается примерно вдвое, поскольку сохраняются и исходный текст, и индекс. Для систем с преобладанием чтения, таких как поиск, этот компромисс практически всегда оправдан.