Инвертированный индекс — сердце поиска

Разбираем структуру, благодаря которой Elasticsearch находит слово среди миллионов документов за миллисекунды.

Инвертированный индекс — структура данных, которая для каждого слова (терма) хранит список документов, где это слово встречается.

От документа к слову — наоборот

Обычное хранилище отвечает на вопрос «какие слова в документе №5?». Поиск же задаёт обратный вопрос: «в каких документах есть слово кофе?». Чтобы отвечать на него мгновенно, индекс строят инвертированным — отображение идёт от слова к документам, отсюда и название.

Как он строится

Пусть есть три коротких документа:

doc1: "кофе с молоком"
doc2: "чай или кофе"
doc3: "молоко и сахар"

Движок разбивает каждый текст на слова (термы), приводит к нижнему регистру и строит таблицу: терм → список документов (постинг-лист).

  Словарь термов     Постинг-листы (где встречается)
  -----------------  ------------------------------
  кофе         -->   [doc1, doc2]
  молоком      -->   [doc1]
  чай          -->   [doc2]
  или          -->   [doc2]
  молоко       -->   [doc3]
  сахар        -->   [doc3]

Теперь запрос «кофе» решается мгновенно: находим терм кофе в словаре (он отсортирован, поиск — как в словаре по алфавиту) и сразу получаем готовый список [doc1, doc2]. Никакого перебора всех документов, как у LIKE.

Что хранится кроме списка

В реальном индексе для каждого терма в каждом документе хранят ещё:

частоту (term frequency) — сколько раз слово встретилось в документе; нужна для оценки релевантности;
позиции — на каком месте стоит слово; нужны для поиска фраз («кофе с молоком» именно подряд);
в скольких документах встречается терм (document frequency) — редкие слова важнее частых.

Как работает под капотом

Словарь термов хранится в отсортированном виде (часто как структура FST — конечный автомат), поэтому найти терм — это логарифмический или почти константный по времени поиск, не зависящий от числа документов. Запрос из нескольких слов — это пересечение или объединение готовых постинг-листов. Например, «кофе И чай» — пересечём [doc1, doc2] и [doc2], получим [doc2]. Списки отсортированы по id документа, поэтому пересечение делается за один проход, очень быстро. Именно поэтому ES ищет по словам на порядки быстрее реляционной БД с LIKE.

Частые ошибки

Думать, что индекс хранит текст как есть. Он хранит термы после анализа: приведённые к нижнему регистру, иногда обрезанные до основы слова. Что именно попадёт в индекс, определяет анализатор (разберём отдельно).
Ожидать поиск по подстроке. Инвертированный индекс ищет по целым термам. Поиск по части слова требует особых приёмов (n-граммы, wildcard), которые работают иначе и медленнее.

Итоги

Инвертированный индекс отображает слово → список документов, а не наоборот.
Поиск слова — это мгновенный лукап в отсортированном словаре термов плюс готовый постинг-лист.
Кроме списка документов хранятся частоты и позиции — основа для релевантности и поиска фраз.