Блог ·

Поиск без индекса

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

Во что обошёлся бы индекс

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

Индекс на диске — это ещё и лишний файл в папке с заметками, а Блокнотик старается не класть туда ничего, чего вы не писали сами.

Что Блокнотик делает вместо этого

При запуске и всякий раз, когда что-то могло измениться, Блокнотик обходит папку с заметками. Для каждого файла .md он сравнивает размер и время изменения с тем, что уже знает, и перечитывает только изменившиеся. В памяти лежат две версии каждой заметки: текст как есть и «свёрнутая» копия — строчными буквами, с е вместо ё и ss вместо ß.

Запрос разбирается на части — слова, фразы в кавычках, -исключения, фильтры tag: — и сворачивается так же. Затем для каждой заметки:

  1. каждая обычная часть запроса должна встречаться в свёрнутом тексте (простой поиск подстроки);
  2. ни одна исключённая встречаться не должна;
  3. фильтры по тегам сверяются со списком тегов заметки.

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

Цифры

В тестах есть замер: 5000 заметок примерно по 300 слов (2 КБ) каждая, всего 10 МБ текста, и запрос rye starter -invoice. На мини-ПК, где разрабатывается Блокнотик, — четырёхъядерной плате x86, ничем не быстрой, — один поиск занимает около 20 миллисекунд. Это меньше, чем можно заметить во время набора. Несколько сотен заметок — около миллисекунды.

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

Что теряется без индекса

Что выигрываем

Результаты поиска всегда в точности соответствуют тому, что лежит на диске прямо сейчас. Нечего перестраивать, нечему портиться, а весь поиск — около 250 строк на Go, которые читаются за десять минут (search.go в архиве с исходниками).

← Все записи