Інвертований індекс

Структура даних, що розв'язує те, чого не вміють B-tree-індекси: пошук слова всередині рядка. Сама структура — слово → список пар (id документа, позиція); позиції відкривають пошук точних фраз і запити за близькістю слів. Підсумок Віктора: «концептуально це все — решта інженерія» (інвертовані індекси). І саме в інженерії живе його бойова історія: він власноруч написав інвертований індекс над 300 TB даних у продакшені — незмінні поденні індекси, геоатрибути, власна мова запитів із парсером на PEG-граматиці, зберігання в MongoDB і паралельні запити по днях — і виступив про це на KyivJS.

Q&A-продовження несе запропоновану глядачем оптимізацію, яка йому дуже сподобалася: розділити індекс на крихітний файл токенів (токен + байтовий offset/довжина, ~2 MB на 88K токенів — реальні словники рідко перевищують 200–300K токенів, тож він цілком уміщається в пам'яті для бінарного пошуку) плюс сирий бінарний файл постингів, що прибирає накладні витрати base64: 1.3 GB → 938 MB, затримка пошуку 15 мс → 5 мс. Його улюблений наслідок: файл постингів може жити на S3 чи CDN і опитуватися через HTTP Range-запити — serverless-повнотекстовий пошук (Q&A до другої частини). Q&A-випуск додає рамку: інвертований індекс і Є тією ефективною структурою — оптимізації міняють серіалізацію (дельта-стиснення, VByte), а не замінюють її (Q&A №1).