Инвертированный индекс (Inverted Index)
Предпосылки: оценка сложности в O(…), B-дерево или хеш-таблица — для организации словаря элементов; массив — для хранения списков документов.
B-дерево ищет по ключу целого значения: найти запись с id = 42 или все записи с salary от 40000 до 60000. Но представим поисковую систему с миллионом документов. Пользователь вводит «ruby» — нужно найти все документы, содержащие это слово. B-дерево здесь не поможет: ключ — это целый документ, а искать нужно внутри его содержимого. Полный перебор миллиона документов с проверкой каждого — O(n), секунды на один запрос. Нужна структура, которая «переворачивает» отношение: от элемента к списку записей, где он встречается.
Forward vs Inverted
Обычный (forward) индекс отвечает на вопрос «что содержит документ X?»:
Документ 1 → [ruby, rails, postgresql]
Документ 2 → [python, django, postgresql]
Документ 3 → [ruby, sinatra]Инвертированный индекс переворачивает вопрос: «в каких документах встречается элемент Y?»:
ruby → [Документ 1, Документ 3]
rails → [Документ 1]
postgresql → [Документ 1, Документ 2]
python → [Документ 2]
django → [Документ 2]
sinatra → [Документ 3]Аналогия из бумажного мира: предметный указатель в конце книги — это инвертированный индекс. Вместо «страница 42 содержит слова X, Y, Z» он говорит «слово X встречается на страницах 42, 87, 156».
Словарь и posting list
Инвертированный индекс состоит из двух частей. Словарь — структура для быстрого поиска элемента по значению. Обычно это B-дерево (если нужен порядок ключей и prefix-поиск) или хеш-таблица (если достаточно точного совпадения). Posting list — для каждого элемента в словаре хранится отсортированный список идентификаторов записей, содержащих этот элемент.
Posting list отсортирован по идентификаторам записей. Сортировка нужна для эффективного пересечения и объединения списков при составных запросах.
Построение и обновление
Чтобы построить инвертированный индекс, документы превращают в набор элементов (слова, теги, ключи). Для каждого элемента поддерживается posting list.
При добавлении документа из него извлекаются элементы (слова, теги, ключи), убираются дубликаты внутри документа, после чего doc_id добавляется в posting list каждого элемента (обычно в конец, если doc_id монотонно растёт). Удаление документа — обратная операция: doc_id удаляется из posting list’ов, или документ помечается удалённым и фильтруется при поиске, а списки периодически пересобираются. Обновление сводится к удалению старых элементов и добавлению новых.
Эффективность
Запрос «найти все документы со словом ruby» без инвертированного индекса требует чтения каждого документа и проверки его содержимого — O(n) документов. С инвертированным индексом: поиск ключа ruby в словаре за O(log K) для B-дерева или O(1) для хеш-таблицы (где K — количество уникальных элементов), затем чтение posting list за O(k), где k — количество совпадений. При миллионе документов и тысяче совпадений это разница между миллионом и тысячей операций чтения.
Пересечение и объединение
Пользователь поисковой системы редко ищет одно слово — обычно запрос составной. Составные запросы сводятся к операциям над posting list’ами. Запрос «ruby AND postgresql» — это пересечение двух отсортированных списков. Два указателя идут по спискам слева направо: если элементы совпадают — добавляем в результат и двигаем оба, иначе двигаем указатель с меньшим элементом. Сложность — O(n + m), где n и m — длины списков.
Запрос «документы, содержащие ruby ИЛИ rails» — это объединение (OR). Аналогичный проход двумя указателями, но в результат добавляется каждый уникальный элемент. Сложность та же — O(n + m).
Применение
Инвертированный индекс — основа полнотекстового поиска. Lucene, Elasticsearch, Solr строят инвертированные индексы по лексемам (нормализованным словам) документов. В базах данных инвертированный индекс используется для поиска по элементам массивов, ключам и значениям JSON-документов, лексемам текстовых полей. PostgreSQL реализует инвертированный индекс в виде GIN (Generalized Inverted Index), обобщая его для работы с произвольными типами данных через operator classes.
Инвертированный индекс решает задачу поиска внутри значений — слов в тексте, элементов в массиве. Это ортогонально задаче поиска по ключу, которую решают B-дерево и хеш-таблица. Для реализации словаря инвертированного индекса используют те же структуры: B-дерево (если нужен prefix-поиск) или хеш-таблица (если достаточно точного совпадения).
Sources
- Manning, Raghavan, Schütze. Introduction to Information Retrieval (inverted index, postings, intersection). https://nlp.stanford.edu/IR-book/
- Lucene docs: overview of indexing and search (inverted index). https://lucene.apache.org/core/
- PostgreSQL docs (current): GIN indexes. https://www.postgresql.org/docs/current/gin.html
Sources
- Manning, Raghavan, Schütze. Introduction to Information Retrieval (inverted index, postings, intersection). https://nlp.stanford.edu/IR-book/
- Lucene docs: overview of indexing and search (inverted index). https://lucene.apache.org/core/
- PostgreSQL docs (current): GIN indexes. https://www.postgresql.org/docs/current/gin.html