Инвертированный индекс: как устроен полнотекстовый поиск и Elasticsearch
Как работает инвертированный индекс: токенизация и анализаторы, posting lists, пересечение списков, сжатие, ранжирование TF-IDF и BM25, сегменты и шардирование, как в Elasticsearch.
Коротко
| Вопрос | Ответ |
|---|---|
| Что это | Словарь «термин → отсортированный список документов, где он встречается» |
| Зачем | Найти документы по словам без полного перебора всех текстов |
Запрос A AND B | Пересечение двух отсортированных списков: или быстрее с пропусками |
| Ранжирование | TF-IDF или BM25: редкое слово весит больше, частое в документе — больше, но с насыщением |
| Масштабирование | Индекс режется на шарды по документам, запрос идёт во все шарды, топ-K сливается |
| Где используется | Lucene, Elasticsearch, OpenSearch, Solr, полнотекстовый поиск в PostgreSQL (GIN) |
- «Инвертированный» — потому что обычное хранение идёт от документа к словам, а индекс переворачивает связь: от слова к документам.
- Качество поиска на 80% решает не структура данных, а анализатор: как текст режется на токены и приводится к нормальной форме.
- На собеседовании тема всплывает в задачах «спроектируйте поиск по твитам / товарам / логам» и как подвопрос в автодополнении и веб-краулере.
Почему не LIKE '%кот%'
Представьте 100 миллионов товаров и запрос «красные кроссовки». Наивный вариант — пройти по всем описаниям и проверить подстроку. Это на каждый запрос, и обычный B-tree-индекс не поможет: индекс базы данных ускоряет поиск по префиксу значения, а не по слову в середине строки.
Кроме скорости, у подстроки плохая семантика: «кроссовки» не найдут «кроссовок», зато %кот% найдёт «скотч» и «котлету». И никакого порядка результатов: какой из тысяч товаров показывать первым?
Инвертированный индекс решает все три проблемы. Работу переносим на время записи: один раз разбираем каждый документ и раскладываем его слова по «корзинам». Запрос потом читает только корзины своих слов.
Анализ текста: от строки к терминам
Прежде чем что-то индексировать, текст проходит через анализатор. В Elasticsearch он состоит из трёх стадий:
- Character filters — чистка сырой строки: убрать HTML-теги, заменить «ё» на «е».
- Tokenizer — нарезка на токены. Стандартный токенизатор режет по границам слов по правилам Unicode, есть варианты для n-грамм, путей, email.
- Token filters — нормализация каждого токена: нижний регистр, удаление стоп-слов («и», «в», «the»), стемминг («кроссовки» → «кроссовк»), синонимы.
Главное правило: запрос должен проходить через тот же анализатор, что и документы. Если документ проиндексирован со стеммингом, а запрос — без, слово «кроссовки» не совпадёт с термином «кроссовк», и поиск молча вернёт пусто. Это классический баг, который всплывает и в продакшене, и в вопросах интервьюера.
Для русского стемминг особенно важен: у одного существительного до 12 форм. Есть два подхода — стеммер (отрезает окончания по правилам, быстро и грубо) и лемматизатор (приводит к словарной форме по морфологическому словарю, точнее и дороже).
Упрощённый анализатор на Python — нижний регистр, нарезка по словам, стоп-слова:
import re from collections import defaultdict STOP = {"и", "в", "на", "the", "a", "of"} def analyze(text): tokens = re.findall(r"\w+", text.lower()) return [t for t in tokens if t not in STOP]
Строим индекс
Для каждого термина храним posting list — список вхождений, отсортированный по doc_id. Каждый элемент (posting) содержит id документа и, если нужны фразовые запросы, позиции слова в документе. Отдельно запоминаем длину каждого документа — она пригодится для ранжирования.
def build_index(docs): index = defaultdict(list) # term -> [(doc_id, [positions])] doc_len = {} for doc_id, text in sorted(docs.items()): terms = analyze(text) doc_len[doc_id] = len(terms) positions = defaultdict(list) for pos, term in enumerate(terms): positions[term].append(pos) for term, pos_list in positions.items(): index[term].append((doc_id, pos_list)) return index, doc_len docs = { 1: "Кот спит на диване", 2: "Собака и кот играют", 3: "Кот ловит мышь, мышь убегает", 4: "Собака спит", } index, doc_len = build_index(docs) print(index["кот"]) # [(1, [0]), (2, [1]), (3, [0])] print(index["мышь"]) # [(3, [2, 3])] print(doc_len) # {1: 3, 2: 3, 3: 5, 4: 2}
Документы обходятся в порядке возрастания id, поэтому списки получаются отсортированными без отдельной сортировки. Это не мелочь: на сортированности держатся и быстрое пересечение, и сжатие.
Словарь терминов (term dictionary) в настоящих движках — не хеш-таблица. Lucene хранит его в виде конечного автомата (FST): он компактный и умеет искать по префиксу, что нужно для запросов кросс* и нечёткого поиска. Идея родственна префиксному дереву.
Булев поиск: пересечение posting lists
Запрос «кот спит» с семантикой AND — это пересечение двух списков doc_id. Списки отсортированы, значит работает техника двух указателей, как в слиянии в сортировке слиянием:
def intersect(a, b): i = j = 0 out = [] while i < len(a) and j < len(b): if a[i] == b[j]: out.append(a[i]) i += 1 j += 1 elif a[i] < b[j]: i += 1 else: j += 1 return out def ids(term): return [d for d, _ in index.get(term, [])] def search_and(query): # Начинаем с самого короткого списка: промежуточный результат меньше terms = sorted(analyze(query), key=lambda t: len(index.get(t, []))) if not terms: return [] result = ids(terms[0]) for t in terms[1:]: result = intersect(result, ids(t)) if not result: break return result print(search_and("кот спит")) # [1] print(search_and("собака кот")) # [2]
Сложность — . Порядок пересечения важен: результат не длиннее самого короткого списка, поэтому начинать надо с самого редкого термина. Это та же оптимизация, что делает планировщик запросов в БД, выбирая порядок JOIN.
OR — слияние списков без дублей, тоже . NOT — проход по списку с вычитанием. Для запроса из терминов в OR используется слияние k списков через кучу.
Когда списки сильно разной длины
Слово «и» встречается в 50 млн документов, а «рекурсия» — в 2 тысячах. Линейное пересечение прочитает все 50 млн элементов ради 2000 совпадений. Решение — не идти по длинному списку шаг за шагом, а прыгать:
- Skip pointers / skip lists. В длинный список встраиваются указатели «вперёд на элементов» или многоуровневый skip list, как в Lucene. Если следующий кандидат далеко, перепрыгиваем целый блок.
- Галопирующий поиск (exponential search). Для каждого элемента короткого списка ищем позицию в длинном: удваиваем шаг 1, 2, 4, 8… пока не перелетим, затем бинарный поиск внутри последнего интервала.
from bisect import bisect_left def gallop_intersect(small, big): out, lo = [], 0 for x in small: step, hi = 1, lo while hi < len(big) and big[hi] < x: lo = hi hi += step step *= 2 k = bisect_left(big, x, lo, min(hi + 1, len(big))) if k < len(big) and big[k] == x: out.append(x) lo = k return out print(gallop_intersect([3, 7], [1, 2, 3, 4, 5, 6, 8])) # [3]
Сложность — , где — длина короткого списка. При это намного лучше .
Фразовые запросы
Запрос "кот спит" в кавычках требует, чтобы слова стояли рядом и в нужном порядке. Для этого и хранились позиции: сначала пересекаем списки документов, затем в каждом общем документе проверяем, что есть позиция у первого слова и у второго.
def phrase(t1, t2): first = dict(index.get(t1, [])) res = [] for doc_id, pos2 in index.get(t2, []): if doc_id in first: s = set(first[doc_id]) if any(p - 1 in s for p in pos2): res.append(doc_id) return res print(phrase("кот", "спит"), phrase("собака", "спит")) # [1] [4]
Обратите внимание: в документе 1 исходный текст «Кот спит на диване», и «на» выкинуто как стоп-слово. Настоящие движки сохраняют позиции исходного текста с «дырками», чтобы фраза «спит диване» не нашлась там, где между словами было «на». В нашем упрощении позиции считаются после фильтрации — так делать не стоит.
Сжатие: почему индекс помещается в память
Posting list для частого слова — десятки миллионов чисел. По 4 байта на число это гигабайты. Выручает сортированность: вместо самих id храним разности соседних (delta encoding, или gaps). Разности маленькие, а маленькие числа кодируются в мало бит.
Простейший вариант — Variable Byte (VByte): 7 бит данных в байте, старший бит помечает последний байт числа.
def vbyte_encode(doc_ids): out = bytearray() prev = 0 for d in doc_ids: gap = d - prev prev = d while gap >= 128: out.append(gap & 0x7F) gap >>= 7 out.append(gap | 0x80) # старший бит = последний байт числа return bytes(out) postings = [5, 17, 130, 131, 1000, 100000] print(len(vbyte_encode(postings)), "байт вместо", len(postings) * 4) # 9 байт вместо 24
Lucene использует более плотные блочные схемы семейства Frame of Reference / PForDelta: числа пакуются блоками по 128 с одинаковой разрядностью, что хорошо ложится на SIMD. Плюс у сжатия есть неочевидный бонус: меньше байт — меньше чтений с диска и промахов кеша, поэтому сжатый индекс часто читается быстрее несжатого.
Ранжирование: TF-IDF и BM25
Булев поиск отвечает «подходит или нет». Пользователю нужен порядок: самые релевантные документы сверху. Две интуиции:
- TF (term frequency) — чем чаще слово в документе, тем документ релевантнее.
- IDF (inverse document frequency) — чем реже слово в коллекции, тем оно информативнее. Совпадение по «рекурсия» говорит больше, чем по «код».
Классический TF-IDF для термина и документа :
где — число документов, — в скольких из них встречается . Оценка документа — сумма по терминам запроса. Обе величины лежат прямо в индексе: — длина posting list, — число позиций.
У TF-IDF две проблемы. Во-первых, линейный TF: документ, где «кот» повторён 100 раз, получает в 100 раз больше очков — подарок спамерам. Во-вторых, длинные документы выигрывают просто потому, что в них больше слов.
BM25 (Okapi BM25, вероятностная модель Робертсона и Спарк Джонс) чинит обе:
- (обычно 1.2) задаёт насыщение TF: при росте tf дробь стремится к , а не растёт бесконечно.
- (обычно 0.75) — сила нормализации по длине: — длина документа, — средняя длина. При длина не учитывается, при — полностью.
- — вариант из Lucene, всегда положительный.
BM25 — модель по умолчанию в Elasticsearch с версии 5.0, до этого там был TF-IDF.
import math def bm25(query, k1=1.2, b=0.75): n = len(doc_len) avgdl = sum(doc_len.values()) / n scores = defaultdict(float) for term in analyze(query): postings = index.get(term, []) df = len(postings) if df == 0: continue idf = math.log(1 + (n - df + 0.5) / (df + 0.5)) for doc_id, positions in postings: tf = len(positions) norm = k1 * (1 - b + b * doc_len[doc_id] / avgdl) scores[doc_id] += idf * tf * (k1 + 1) / (tf + norm) return sorted(scores.items(), key=lambda x: -x[1]) for doc_id, score in bm25("кот мышь"): print(doc_id, round(score, 3)) # 3 1.73 # 1 0.368 # 2 0.368
Документ 3 содержит оба слова, причём «мышь» — редкое и встречается дважды. Документы 1 и 2 совпали только по «кот», который есть в трёх документах из четырёх, поэтому вклад маленький.
Перебирать все документы для подсчёта не нужно: движки считают оценку только для документов из posting lists и держат кучу на лучших. Алгоритмы вроде WAND и Block-Max WAND (в Lucene с версии 8) ещё и пропускают документы, которые заведомо не попадут в топ-K, используя верхние границы оценок блоков.
Как индекс живёт на диске: сегменты
Posting lists сжаты и отсортированы, вставлять в середину дорого. Поэтому Lucene устроен как LSM-дерево:
- Новые документы копятся в памяти, затем сбрасываются в сегмент — маленький неизменяемый инвертированный индекс.
- Поиск идёт по всем сегментам и объединяет результаты.
- Удаление не трогает сегмент: документ помечается в битовой маске удалённых. Обновление = удаление + новая версия.
- Фоновый merge сливает мелкие сегменты в крупные и физически выкидывает удалённые документы.
В Elasticsearch сброс в новый сегмент называется refresh и по умолчанию происходит раз в секунду. Отсюда термин near real-time: документ становится видимым в поиске не сразу после записи, а через ~1 секунду. Надёжность до записи сегмента на диск обеспечивает журнал транзакций (translog) — тот же приём, что WAL в базах данных.
Шардирование: индекс, который не влезает в одну машину
Когда документов миллиарды, индекс режут на части. Два принципиально разных способа:
| Способ | Как режем | Запрос | Плюсы и минусы |
|---|---|---|---|
| По документам (document-partitioned) | Каждый шард — полный индекс своих документов | Во все шарды (scatter-gather) | Просто, равномерно, но каждый запрос нагружает все шарды |
| По терминам (term-partitioned) | Шард хранит posting lists части слов | Только в шарды с терминами запроса | Меньше шардов на запрос, но пересечение через сеть и горячие слова |
Почти все реальные системы, включая Elasticsearch, выбирают разбиение по документам. Пересечение списков остаётся локальным, а нагрузку на частые слова равномерно делят все шарды.
Как это устроено в Elasticsearch
- Индекс состоит из primary-шардов, каждый шард — отдельный индекс Lucene. У каждого primary есть реплики на других узлах. Подробнее о самих подходах — в статье про шардирование и репликацию.
- Маршрутизация документа:
shard = hash(_routing) % number_of_primary_shards, где_routingпо умолчанию — id документа. Поэтому число primary-шардов нельзя просто поменять у живого индекса: изменится остаток от деления, и документы «потеряются». Есть API_splitи_shrinkс жёсткими ограничениями по кратности, а в общем случае — переиндексация. Это прямая противоположность консистентному хешированию, и интервьюер может спросить, почему так: зато маршрутизация тривиальна и не нужна таблица распределения. - Поиск идёт в две фазы (query then fetch). Координирующий узел рассылает запрос по одной копии каждого шарда. Фаза query: каждый шард возвращает только
(doc_id, score)своих топ-K. Координатор сливает списки и выбирает глобальный топ-K. Фаза fetch: координатор запрашивает полные документы только у тех шардов, чьи документы попали в итог.
import heapq shard_results = [ [(9.1, "a"), (7.4, "b"), (3.0, "c")], [(8.8, "d"), (8.0, "e"), (1.2, "f")], [(9.5, "g"), (2.1, "h"), (0.5, "i")], ] top3 = heapq.nlargest(3, (hit for shard in shard_results for hit in shard)) print(top3) # [(9.5, 'g'), (9.1, 'a'), (8.8, 'd')]
Каждый шард обязан вернуть кандидатов, ведь все глобальные лучшие могут лежать в одном шарде. Отсюда проблема глубокой пагинации: страница from=10000, size=10 заставляет каждый из шардов отдать 10 010 записей, а координатор сортирует . Поэтому Elasticsearch по умолчанию ограничивает from + size значением 10 000 и предлагает search_after — курсорную пагинацию.
Ловушка: локальный IDF
BM25 зависит от и , а каждый шард считает их по своим документам. Если слово случайно скопилось в одном шарде, там его IDF ниже, и одинаковые документы получают разные оценки в зависимости от того, куда попали. На больших индексах с равномерной маршрутизацией эффект размывается, а на маленьких тестовых бывает очень заметен: «почему у меня в тесте странный порядок?».
Решение — режим dfs_query_then_fetch: перед основным запросом координатор собирает статистику терминов со всех шардов и считает глобальный IDF. Цена — лишний сетевой раунд, поэтому по умолчанию он выключен.
Сколько шардов делать
Шард — это не бесплатно: у каждого свои сегменты, кеши, файловые дескрипторы и потоки поиска. Тысячи мелких шардов перегружают кластер и метаданные мастера. С версии 7.0 Elasticsearch по умолчанию создаёт 1 primary-шард на индекс (раньше было 5). В документации Elastic ориентиром называют шарды размером от 10 до 50 ГБ. Для логов вместо одного огромного индекса делают индексы по времени (по дню или по объёму, через rollover): старые легко удалить целиком, а запросы по последним часам трогают только свежие индексы.
Как отвечать на собеседовании
Если просят спроектировать поиск, удобная последовательность:
- Требования. Объём документов, QPS запросов и записи, нужна ли свежесть за секунды, нужны ли фразы, опечатки, фильтры по полям.
- Индексация. Источник правды — основная БД, в поисковый движок данные едут асинхронно через очередь или CDC. Поисковый индекс — производная структура, его можно перестроить.
- Анализатор. Токенизация, нижний регистр, стемминг или лемматизация для русского, синонимы. Один и тот же для документов и запросов.
- Структура. Term dictionary → posting lists с id, частотами и позициями. Сжатие разностями.
- Запрос. Пересечение с самого короткого списка, skip-указатели, BM25, топ-K через кучу.
- Масштаб. Шардирование по документам, реплики для чтения и отказоустойчивости, scatter-gather, глобальный IDF при необходимости, ограничение глубокой пагинации.
- Оценки. Сделайте прикидку на салфетке: размер индекса обычно 20–50% от исходного текста, нужно ли держать его в RAM.
Типичные ошибки
- Разные анализаторы при индексации и поиске — поиск молча ничего не находит.
- Пересечение с самого длинного списка — в разы медленнее, чем с самого редкого термина.
- Хранить позиции «на всякий случай» — индекс заметно вырастает. Если фразовые запросы не нужны, позиции отключают.
- Считать поисковый движок основной базой. Elasticsearch — не транзакционное хранилище, refresh даёт задержку видимости, а переиндексация — штатная операция.
- Много мелких шардов «на вырост» — накладные расходы кластера растут быстрее, чем польза.
- Глубокая пагинация через
from— вместо неёsearch_afterили scroll/point-in-time для выгрузок.
Итог
Инвертированный индекс — это отсортированные списки документов для каждого слова. Всё остальное следует из сортированности: пересечение двумя указателями или прыжками, сжатие разностями, слияние сегментов, топ-K через кучу. Ранжирование BM25 строится на тех же списках: длина списка даёт IDF, число позиций — TF. А масштабирование в Elasticsearch — это много независимых индексов Lucene по документам и координатор, который рассылает запрос и сливает лучшие результаты.