Получить доступ

Как устроен инвертированный индекс и почему он быстрее LIKE '%слово%'?

MiddleПолнотекстовый поискElasticsearch
Ещё спрашивают так:
  • Как работает полнотекстовый поиск?
Коротко

Инвертированный индекс — не «документ → слова», а «слово → документы». Поиск слова — прочитать готовый список документов, а не перебирать тексты.

  • При индексации текст разбивается анализатором на термины
  • Списки отсортированы — пересечение для нескольких слов быстрое
  • Ранжирование по частоте термина и редкости (BM25)

А ещё LIKE '%слово%' читает всю таблицу и не понимает словоформ

Так подсказку видит пользователь sotto на живом собеседовании — за пару секунд, пока вы думаете вслух.

Подробно

Запрос с ведущим шаблоном заставляет базу просмотреть каждую строку и каждый её символ — стоимость линейна по объёму текста. Инвертированный индекс переносит эту работу на этап индексации: текст один раз разбирается на термины, и для каждого термина хранится список документов с позициями. Поиск нескольких слов превращается в пересечение готовых списков, что очень быстро. Плата — индекс нужно строить и хранить, а результат виден не мгновенно: изменения становятся доступны для поиска после обновления индекса, то есть согласованность здесь в конечном счёте.

Что хотят услышать

  • Устройство инвертированного индекса.
  • Почему быстрее LIKE.
  • Анализ текста и ранжирование.

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

  • Ожидать, что документ станет доступен для поиска сразу после записи.
  • Строить полнотекстовый поиск на LIKE, когда объём вырос.

Проверьте себя

Один верный вариант. Подумайте, потом откройте ответ.

Показать варианты и ответ
  • ✓Он хранит отображение «термин → список документов, где термин встречается», поэтому поиск сводится к чтению готового списка вместо просмотра всех текстов
  • ✗Он хранит документы в отсортированном по алфавиту порядке
  • ✗Он сжимает тексты, за счёт чего сканирование выполняется быстрее
  • ✗Он кэширует результаты ранее выполненных запросов

Что спросят дальше

  • Что происходит с текстом на этапе анализа?
  • Почему поисковый индекс не делают источником истины?

Разбор темы

Связанные вопросы

Закрытая бета

Подсказки на собеседовании — в реальном времени

sotto слышит вопрос интервьюера и показывает короткий ответ и план, как в блоке «Коротко». Оставьте контакт — пришлём доступ и промокод.

  • Промокод на 2 часа — сверх пробных 30 минут
  • Программа для Windows — скачать сразу, войти — через Яндекс ID или VK ID
  • Прямая связь с разработчиком: что улучшить — сделаем