Инвертированный индекс (Inverted Index)
Предпосылки: оценка сложности в O(…), бинарный поиск, ссылки, B-дерево или хеш-таблица — для организации словаря элементов; массив — для хранения списков документов.
← B-дерево
B-дерево ищет по ключу целого значения: найти запись с id = 42 или все записи с salary от 40000 до 60000. Ключ заранее известен целиком — мы спрашиваем «дай запись, у которой это поле равно такому-то значению».
Но представим поисковую систему с миллионом документов. Пользователь вводит «ruby» — нужно найти все документы, содержащие это слово. Это другой вопрос: документ — большой текст из сотен слов, и «ruby» — не значение всего поля, а одно слово где-то внутри. Если построить B-дерево по самому тексту документа как по ключу, оно упорядочит документы целиком и поможет найти документ, равный заданному тексту, — но не документы, у которых заданное слово где-то в середине. Полный перебор миллиона документов с проверкой каждого на наличие слова — O(n), секунды на один запрос.
Нужна структура, которая «переворачивает» отношение: вместо «документ → его слова» хранить «слово → документы, где оно встречается». Тогда по слову «ruby» сразу доступен готовый список документов.
Прямое и перевёрнутое представление
Если хранить, какие слова лежат в каждом документе, получается прямое представление — оно отвечает на вопрос «что содержит документ 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».
Словарь и списки вхождений
Инвертированный индекс состоит из двух частей. Первая — словарь: структура для быстрого поиска элемента по значению. По введённому слову нужно за доли секунды найти его строку в индексе, а не перебирать все слова. Обычно словарь хранят как B-дерево (если важен порядок ключей — тогда возможен поиск по началу слова: rub находит и ruby, и rubygems) или хеш-таблицу (если достаточно точного совпадения).
Вторая часть — список вхождений (posting list, от англ. posting — «запись о вхождении»): для каждого элемента словаря хранится список идентификаторов документов, в которых этот элемент встречается. Идентификатор документа — небольшое число doc_id, выданное каждому документу при добавлении в индекс; вместо тяжёлого текста в списках лежат именно числа.
Список вхождений держат отсортированным по doc_id. Зачем — станет видно ниже, когда запрос объединит несколько слов: по отсортированным спискам это делается одним проходом.
Построение и обновление
Чтобы построить инвертированный индекс, документы превращают в набор элементов (слова, теги, ключи). Для каждого элемента поддерживается свой список вхождений.
При добавлении документа из него извлекаются элементы, убираются дубликаты внутри документа (одно слово в документе — одно вхождение), после чего doc_id нового документа дописывается в список каждого его элемента. Если каждый новый документ получает doc_id больше предыдущего (нумерация только растёт), то новый doc_id крупнее всех уже лежащих в списке — его кладут в конец, и список остаётся отсортированным без дополнительной работы.
Удаление сложнее, потому что вырезать doc_id из середины каждого списка дорого: документ мог попасть в тысячи списков. Поэтому документ обычно не убирают сразу, а помечают удалённым в отдельном множестве; при поиске такие doc_id отбрасываются из результата. Списки при этом продолжают расти за счёт мёртвых записей, поэтому время от времени их пересобирают заново, уже без удалённых doc_id, — точечное удаление заменяется одной редкой массовой операцией. Обновление документа — это его удаление и добавление заново с новым содержимым.
Эффективность
Запрос «найти все документы со словом ruby» без инвертированного индекса требует чтения каждого документа и проверки его содержимого — O(n) документов. С инвертированным индексом: поиск ключа ruby в словаре за O(log K) для B-дерева или O(1) для хеш-таблицы (где K — количество уникальных элементов), затем чтение posting list за O(k), где k — количество совпадений. При миллионе документов и тысяче совпадений это разница между миллионом и тысячей операций чтения.
Пересечение и объединение
Пользователь поисковой системы редко ищет одно слово — обычно запрос составной. Такой запрос сводится к операциям над списками вхождений. Запрос «ruby AND postgresql» («оба слова») — это пересечение двух списков: нужны doc_id, которые есть в обоих.
Здесь и пригождается сортировка списков по doc_id. По каждому списку движется свой указатель, оба стартуют слева, с наименьших doc_id. На каждом шаге сравниваются два doc_id под указателями: совпали — этот документ содержит оба слова, кладём его в результат и сдвигаем оба указателя; не совпали — сдвигаем тот указатель, под которым doc_id меньше. Сдвиг именно меньшего корректен потому, что списки отсортированы: меньший doc_id дальше по второму списку уже не встретится (там идут только бо́льшие значения), значит, в пересечение он не попадёт и его можно пропустить. Каждый указатель проходит свой список ровно один раз, поэтому сложность — O(n + m), где n и m — длины списков.
Запрос «ruby ИЛИ rails» («хотя бы одно слово») — это объединение списков. Проход теми же двумя указателями, но в результат идёт каждый встреченный doc_id, а одинаковые при совпадении берутся один раз. Сложность та же — O(n + m).
Применение
Инвертированный индекс — основа полнотекстового поиска (поиска документов по словам внутри текста). На нём построены поисковые движки Lucene, Elasticsearch, Solr: каждый сначала приводит слова к единой форме (например, Ruby, RUBY, ruby — к одному ruby, чтобы регистр и словоформа не мешали совпадению), а затем строит инвертированный индекс по этим нормализованным словам. Та же структура работает и в базах данных — для поиска по элементам массивов или по словам в текстовых полях. PostgreSQL реализует инвертированный индекс под именем GIN (обобщённый инвертированный индекс), расширяя идею на разные типы значений, а не только слова в тексте.
Инвертированный индекс отвечает на вопрос «в каких записях встречается это значение?» — поиск внутри содержимого: слов в тексте, элементов в массиве. Это другой вопрос, чем «найди запись по её ключу», на который отвечают B-дерево и хеш-таблица; они здесь не конкуренты, а соседи. Больше того, словарь самого инвертированного индекса строится на тех же B-дереве (когда нужен поиск по началу слова) и хеш-таблице (когда достаточно точного совпадения) — поиск по ключу обслуживает поиск внутри значений.
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
← B-дерево