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

В первом уроке PostgreSQL искал «пиццу» полным проходом: брал каждую строку и проверял, нет ли в ней нужных букв. Elasticsearch на миллионе блюд отвечает за миллисекунды. Секрет не в мощном железе, а в том, что он вообще не перебирает документы. Вместо этого у него есть структура, которая сразу знает, где лежит каждое слово.

Предметный указатель

Открой в конце толстого учебника предметный указатель. Там по алфавиту стоят слова, а рядом номера страниц: «гранула, 112, 140», «индекс, 23, 57, 112». Чтобы найти, где в книге говорится про гранулы, ты не листаешь все пятьсот страниц. Ты находишь слово в указателе (он отсортирован, это быстро) и сразу получаешь список страниц.

Обычная таблица устроена наоборот: «страница → её текст». Указатель переворачивает её: «слово → страницы». Поэтому его и называют инвертированным индексом.

Как он выглядит

Elasticsearch при записи документа разбирает его текст на термины: обычно это слова, приведённые к нижнему регистру. Для каждого термина в индексе хранится:

• список документов, где термин встречается (по-английски postings list);
• позиции термина в каждом документе: нужны, чтобы искать фразы «пицца с грибами» с учётом порядка слов;
• частоты: сколько раз термин встретился в документе и в скольких документах вообще. Они понадобятся для оценки релевантности в уроке про BM25.

Сам словарь терминов отсортирован, поэтому нужный термин находится за несколько шагов, как слово в указателе.