На миллионе синтетических записей сжатый индекс выполнял запросы из редкого и частого слова примерно в пять раз быстрее простого пересечения массивов. Хороший результат — до тех пор, пока перебор редких кандидатов не появился у несжатого индекса. Тогда обычный Uint32Array оказался ещё вдвое быстрее.

Потом обнаружилась другая неприятность: секция индекса занимала около 9 МиБ, но держала в памяти файл на 137 МиБ. Для этого хватило одной строки с subarray.

Ниже — устройство небольшого поисковика на JavaScript и разбор этих двух находок. У него есть бинарный формат, поиск в Worker, локальные правки и сохранение в IndexedDB. Код можно запустить, а числа — пересчитать. Измерения на миллионе синтетических записей выполнены в Node.js; браузерное демо работает с 32 772 реальными товарами.

Что именно должен находить поиск

Возьмём каталог с тремя полями: ID, название и бренд. Пользователь вводит чай черный; нужны товары, в которых встретились оба слова. Они могут находиться в разных полях, порядок не важен. Регистр и различие е/ё убираем, слова нормализуем через NFKC. Числовой на вид ID оставляем строкой: 007 — самостоятельный идентификатор.

Это намеренно узкая задача. «Чёрного чая» не превращается в «черный чай», опечатки не исправляются, релевантность не считается. Полное совпадение с ID имеет приоритет, остальные ответы сортируются по ID. Без фиксированных правил легко «ускорить» поиск, который незаметно начал возвращать другой ответ.

Внешние ID неудобно таскать по всем спискам, поэтому внутри снимка каталога выдаём документам плотные номера. Например, A → 0, B → 1, C → 2. Для каждого слова храним отсортированные номера документов, где оно есть:

A: чай черный,  север
B: чай зеленый, север
C: кофе черный, юг

чай     → [0, 1]
черный  → [0, 2]
кофе    → [2]

Такие списки обычно называют postings. Найти чай черный — значит пересечь [0, 1] и [0, 2]. Получится [0], а пользователю вернётся товар A. Миллион уникальных внешних ID в текстовый словарь не добавляем: для полного совпадения есть отдельный бинарный поиск по карточкам.

Писать ещё одну универсальную поисковую библиотеку здесь незачем. Свой небольшой движок нужен, чтобы можно было заменить ровно одну деталь и увидеть её цену.

Ускорение, которое досталось не тому

Начальная реализация пересекает два списка двумя указателями. Номера совпали — добавили в ответ и двинулись дальше. Не совпали — продвинули указатель меньшего номера. Удобно, последовательно, верхняя оценка работы — O(a + b).

Но представьте запрос из очень редкого и очень частого слова. Ради нескольких кандидатов приходится проходить большую часть длинного списка. Можно сделать наоборот: перебирать короткий список, а каждый его номер искать в длинном бинарным поиском. Дальше буду называть эти планы merge и probe.

Смысл probe укладывается в несколько строк. Списки уже отсортированы по длине; binaryContains — обычная проверка бинарным поиском:

const [shortest, ...rest] = lists;

for (const docID of shortest) {
  if (rest.every(list => binaryContains(list, docID))) {
    result.push(docID);
  }
}

Для двух списков грубая оценка — O(a log b), где a ≤ b. Когда a мало, это привлекательно. Когда оба списка длинные, последовательный проход может оказаться дешевле множества бинарных поисков. Начинать пересечение с редких слов — давно известная идея, но здесь важно другое: для неё вообще не нужно сжатие.

Поэтому сравним четыре варианта: обычные и сжатые списки, в каждом — merge и probe. У сжатого merge сначала полностью декодируются нужные списки, затем выполняется пересечение. Сжатый probe читает кратчайший список целиком, а в остальных декодирует только блоки, необходимые для проверки кандидатов. Как устроены блоки, разберём чуть ниже.

Миллион синтетических документов. Столбик — медиана медиан трёх процессов, тонкий отрезок — минимум и максимум между ними. У двух панелей разные линейные шкалы; сравнивать длины столбиков между панелями нельзя.

На запросах «редкое + частое» обычный merge занял 0,335 мс, сжатый probe — 0,066 мс. Если остановиться на этой паре, выигрыш легко приписать сжатию. Но несжатый probe дал 0,033 мс. Основную работу сделал выбор плана: мы перестали читать почти весь длинный список.

На двух частых словах всё иначе. Обычный merge — 7,45 мс, обычный probe — 14,74 мс, сжатый probe — 17,61 мс. Кандидатов много; проверять каждого по отдельности уже невыгодно. Полное декодирование с последующим merge в этой реализации ещё дороже: 54,22 мс.

Сжатый probe тоже умеет выигрывать у несжатого. В отдельной группе запросов, где оба слова существуют, но их списки не пересекаются, получилось 9,28 против 15,68 мс. Однако у этих реализаций есть ещё одно различие: одна ищет внутри небольшого декодированного блока, другая — по всему массиву. Чтобы объяснить разницу именно кэшем или сжатием, нужен дополнительный контроль с несжатыми блоками. В текущем опыте его нет.

Автоматического выбора плана в прототипе пока нет. Разумный следующий эксперимент — менять соотношение длин списков и искать, где merge начинает проигрывать probe. Получить из этого сравнения универсальный порог было бы слишком смело.

Откуда числа. Node 24.15, Windows, Core Ultra 7 155H, 15,5 ГиБ RAM. На каждый вариант — три свежих процесса. После построения индекса выполняются два прогревочных прохода по набору запросов, затем три измеряемых; порядок вариантов и запросов перемешан. В каждой показанной группе восемь разных запросов. Фоновая нагрузка рабочей машины не контролировалась, поэтому диапазоны показывают разброс этого опыта, а не гарантированные задержки.

Измеряется получение полного массива внутренних docID. Преобразование в карточки и внешние ID, Worker, IndexedDB и отрисовка сюда не входят. После остановки таймера количество и хеш результатов сверяются с независимым линейным поиском. Полная матрица, другие размеры каталога и диапазоны сохранены вместе с кодом.

Как не распаковывать весь список

У возрастающих номеров документов часто маленькие разности. Вместо [1000, 1003, 1010] можно записать первое число и два приращения: [1000, 3, 7]. Затем закодировать их varint: семь полезных бит на байт, старший бит сообщает, будет ли продолжение.

В base-128 varint наш пример выглядит как e8 07 03 07: четыре байта вместо двенадцати у Uint32Array. Выглядит хорошо, пока не потребуется найти число в середине потока. Чтобы восстановить его значение, нужны предыдущие приращения.

Разрежем длинный список на независимые блоки по 128 номеров. Каждый начинается абсолютным значением, а в каталоге блоков лежат первый и последний docID, смещение, длина в байтах и число элементов. По границам можно найти нужный блок, не трогая остальной поток.

Ниже блоки по восемь элементов, чтобы весь пример помещался на картинке. Проверяем кандидатов [3, 5, 12, 20] в списке [1…8, 17…24, 33…40].

Для 3 декодируется первый блок. Для 5 используется тот же результат. Число 12 попадает в промежуток между диапазонами — читать поток вообще не нужно. Для 20 открывается второй блок. Третий блок не декодируется: его границы в каталоге проверяются, но сам поток остаётся сжатым. Ответ — [3, 5, 20].

Каталог блоков, конечно, тоже занимает место: пять Uint32, то есть 20 байт на блок. Если применить его к трём числам из предыдущего примера, получатся 24 байта вместо исходных двенадцати. Поэтому короткие списки устроены отдельно: одиночный docID лежит прямо в словаре, от двух до восьми номеров — в коротком массиве Uint32. Блоки начинаются после восьми. Эти пороги выбраны для прототипа без отдельного сравнения вариантов.

А теперь неприятная бухгалтерия. На миллионе документов все несжатые postings занимают 23,65 МиБ. Сжатый поток вместе с каталогом блоков — 10,57 МиБ. Но весь сжатый файл всё равно весит 136,80 МиБ: примерно 91% занимают JSON-карточки товаров.

Если сравнить его с расчётным контейнером, где те же карточки соседствуют с обычными Uint32-списками, экономия всего файла — 8,7%. Размер несжатого контейнера рассчитан по его составу; код для чтения такого формата не написан.

Это хороший момент остановить работу над varint. Пока в файле лежат 124,64 МиБ карточек, ещё несколько процентов от postings мало изменят загрузку каталога. Следующая серьёзная экономия требует другого представления самих документов.

Девять мегабайт, которые держали сто тридцать семь

Файл открывается примерно так: прочитать байты, проверить заголовок и контрольную сумму, разобрать JSON-карточки, сохранить секцию postings. Последний шаг выглядел невинно:

const postings = bytes.subarray(offset);

Никакой лишней копии. Поля документов уже разобраны. В postings.byteLength — только нужная секция. Остальное сборщик мусора, кажется, должен убрать.

Но subarray возвращает представление того же ArrayBuffer. Маленькое окно продолжает ссылаться на большой буфер. Удерживается весь файл — вместе с байтами JSON, который уже существует ещё и в виде объектов.

Посмотреть на это можно без профилировщика:

let file = new Uint8Array(128 * 1024 * 1024);
const tail = file.subarray(file.length - 1024);
file = null;

console.log(tail.byteLength);        // 1024
console.log(tail.buffer.byteLength); // 134217728

Представление длиной в килобайт по-прежнему удерживает весь буфер на 128 МиБ. Для каталога исправление оказалось таким:

const postings = Uint8Array.from(bytes.subarray(offset));

Именно явная копия в Uint8Array: если на входе Node Buffer, его slice() тоже создаст представление. По привычке заменить одно имя метода другим здесь недостаточно.

Сверху — связь объектов, без соблюдения масштаба. Снизу — измеренные ArrayBuffer всего процесса после удаления ссылки на вход и GC. Это две разные величины: размер буфера секции и общий счётчик процесса.

Один и тот же файл открывался в трёх свежих процессах для каждого режима. После удаления внешней ссылки на вход и принудительного GC счётчик ArrayBuffer процесса уменьшился с 138,57 до 10,59 МиБ. Разница — почти 128 МиБ удерживаемых буферов, без изменения формата и алгоритма поиска. Такой же спад RSS или немедленный возврат памяти операционной системе из этого не следует.

У копирования есть цена: пока исходный файл жив, в памяти находятся оба буфера. И если вызывающий код сохранил свою ссылку на файл, избавиться от него внутри читателя не получится. Это исправление времени жизни данных, а не бесплатное уменьшение пикового потребления.

Куча объектов в этом опыте осталась примерно 231 МиБ. Время открытия колебалось настолько, что обещать ускорение нельзя. Миллион товаров по-прежнему дорог в памяти, просто теперь он не удерживает ещё одну ненужную копию большей части исходных данных.

Переименовать товар сложнее, чем добавить слово

До этого индекс был неподвижным. Но пользователь может переименовать A из «чай черный» в «кофе черный», а товар C удалить. Если только добавить новые postings, старое слово «чай» продолжит находить A.

Пересобирать миллион карточек после каждой правки не хочется. Код обновлений не меняет базу: правки складываются в отдельный Map:

new Map([
  ['A', {id: 'A', name: 'кофе черный', brand: 'север'}],
  ['C', null],
]);

Наличие ID в этой карте скрывает его старую версию — независимо от того, лежит там новая карточка или null. Живые карточки получают свой небольшой индекс. При поиске берём совпадения базы, отбрасываем затронутые ID и добавляем совпадения изменений. Теперь чай черный не находит ничего, а кофе черный возвращает только A.

Карта изменений — delta — со временем растёт. В прототипе её индекс пересобирается при каждой пачке правок. Подготовка ещё одной правки при 100 затронутых ID заняла 0,65 мс; при 10 тысячах — 47,77 мс. Это медианы трёх процессов, диапазоны — 0,57–0,82 и 24,87–64,74 мс соответственно. Каждое измерение начинается с одинакового снимка; оно не накапливает новые изменения поверх предыдущего.

Время полного поиска при этом заметно гуляло. Из этих измерений нельзя вывести аккуратную кривую «вдвое больше delta — вдвое медленнее поиск». При 10 тысячах ID запись состояния head занимает примерно 1 МиБ: в ней хранится вся карта изменений.

Чтобы убрать delta, нужна компактация: собрать актуальные документы в новую базу и очистить карту. На миллионе записей с 10 тысячами изменений она заняла 9,72 секунды, диапазон трёх запусков — 5,56–10,18 секунды. Это вычисления в Node, без записи в IndexedDB.

Вычисления выполняются в Worker, отдельно от интерфейса. Но команды в нём идут последовательно: пока Worker собирает новую базу, следующий поиск ждёт. При новом вводе интерфейс сразу помечает прежний запрос устаревшим — ещё до задержки debounce. Поздний ответ или ошибка этого запроса уже не попадут на экран. Начатую работу и очередь запросов это не отменяет. Для поиска без такой паузы понадобятся второй Worker и переключение между снимками. В этом прототипе их пока нет.

Ещё одна деталь, которую легко пропустить в демо: интерфейс рисует 30 карточек, а движок перед этим получает все совпадения, фильтрует старые версии и сортирует ответ. limit: 30 пока экономит отрисовку, но не всю работу поиска.

Две вкладки и одно сохранение

Осталось не потерять правки. prepare создаёт новый Catalog, не меняя текущий; код переключается на него только после успешного сохранения. В IndexedDB два хранилища объектов: bases с бинарными базами и state с записью head. В ней лежат номер поколения, ключ базы и delta.

У снимка есть и менее очевидный враг — вызывающий код. Если вернуть ему сам объект карточки, присваивание result.documents[0].name = 'кофе' изменит документ, а postings останутся прежними. Поэтому приложение открывает каталог через openCatalog: внутренний экземпляр закрыт в замыкании, наружу возвращаются копии карточек и состояния. Низкоуровневое ядро оставлено отдельно для экспериментов. Приведённые времена поиска, подготовки delta и компактации измерены в нём; защитное копирование на границе приложения в них не входит.

Допустим, две вкладки прочитали поколение 4. Обе подготовили изменения. Первая записала поколение 5. Вторая должна обнаружить конфликт, а не молча затереть её результат.

Ключевая часть сохранения выглядит так; state получен из уже открытой readwrite-транзакции:

const request = state.get('head');

request.onsuccess = () => {
  const old = request.result;

  if ((old?.generation ?? -1) !== expected) {
    tx.abort();
    return;
  }

  state.put(nextHead, 'head');
};

Проверка поколения и запись находятся внутри одной транзакции. Если сначала проверить версию, потом отдельно записать, между действиями остаётся то самое окно для второй вкладки. При компактации туда же входят запись новой базы и удаление старой. Новый Catalog устанавливается только после события complete.

Хеширование и сборка заканчиваются до открытия транзакции: у IndexedDB есть собственные правила её активности, произвольный await посреди сохранения здесь не нужен. При конфликте автоматического слияния нет — надо прочитать актуальное состояние и повторить правку.

В браузере проверены сохранение после перезагрузки, намеренный abort и конфликт двух вкладок. Abort оставляет предыдущий снимок. Отключение питания в этом опыте не проверялось.

Что можно забрать в свой проект

Самым полезным результатом оказался контрольный Uint32Array: он отделил выигрыш алгоритма от выигрыша представления. Когда меняется и формат, и способ поиска, красивая цифра ещё не объясняет, что именно помогло.

С памятью помогло сравнение byteLength и buffer.byteLength. Их разница сразу объяснила, куда делась память. Такой же вопрос стоит задать любому парсеру, который оставляет маленькое представление на входной пакет.

А обновления быстро вывели разговор за пределы пересечения списков. Здесь уже важны видимость старых версий, длительность компактации и момент, когда запись считается принятой. Без этого быстрый поиск остаётся хорошим микробенчмарком.

Следующий шаг для этого движка — несжатые блоки как дополнительный контроль, потоковое пересечение сжатых списков и измерение порога выбора плана. Для приложения к ним добавились бы компактные карточки и компактация во втором Worker. С готовыми библиотеками этот проект пока не сравнивался; оснований предлагать его вместо них нет.

Запустить и проверить

Комплект проекта содержит исходники, демо, корпус, сырые измерения и подробную методику. Для запуска после распаковки перейдите в каталог lab:

node --test test/*.test.mjs
node scripts/serve.mjs

Нужен Node.js 24+. У ядра нет runtime-зависимостей. matrix.mjs и lifecycle.mjs из папки scripts повторяют измерения; синтетический миллион генерируется локально. Для полной пересборки нужен запас в несколько гигабайт RAM. Все команды и детали — в README.

Реальные 32 772 записи — сохранённое подмножество Open Food Facts, снимок от 5 августа 2026 года, условия ODbL/DbCL. Это отдельный корпус, не источник синтетического миллиона. После загрузки поиск работает локально. Для повторного открытия демо сервер должен быть запущен: автономного запуска без него пока нет.

Если будете повторять опыт, особенно интересно проверить границу между merge и probe на своём распределении слов. У каталога запчастей, продуктовой базы и списка файлов она вполне может оказаться разной.