Blog ·
Search without an index
Most search engines build an index: a table from words to the documents that contain them. Blocknotik doesn't have one. Every time you type a letter in the search box, it goes through the full text of every note. That sounds wasteful, so here are the reasons and the numbers.
What an index would cost
An index is a second copy of your notes in another shape. It has to be built at the first start, updated on every save, and kept in sync with files that other programs change behind its back — a sync tool, Git, an editor on another computer. When the two disagree, you get the worst kind of bug: a note that exists but can't be found.
An index on disk is also one more file in your notes folder, and Blocknotik tries not to put anything there that you didn't write.
What Blocknotik does instead
At start, and again whenever something might have changed, Blocknotik walks through the notes folder. For each .md file it compares size and modification time with what it already knows and reads only files that changed. It keeps two versions of every note in memory: the text as it is, and a “folded” copy in lower case with ё replaced by е and ß by ss.
A query is split into terms — words, phrases in quotes, -exclusions, tag: filters — and folded the same way. Then for each note:
- every positive term must occur in the folded text (a plain substring search);
- no negative term may occur;
- tag terms are checked against the note's tag list.
Matching notes get a score: a lot for a word in the title, a bit for each occurrence in the text (capped at ten per word, so one huge note doesn't drown everything), and ties go to the newer note. The top 200 are returned with an excerpt around the first match.
The numbers
The test suite includes a benchmark: 5,000 notes of about 300 words (2 KB) each, 10 MB of text in total, and the query rye starter -invoice. On the mini PC Blocknotik is developed on — a four-core x86 board, nothing fast — one search takes about 20 milliseconds. That's below what you can notice while typing. A few hundred notes take about a millisecond.
The time grows linearly with the amount of text. At 100 MB of notes, a search would take roughly 200 ms, which you'd feel. We don't think many people keep that much text in personal notes, but if you do, Blocknotik isn't the right tool yet, and we'd rather say so.
What you lose without an index
- No stemming or language rules. Substring matching covers most word endings (
ржанfinds ржаная and ржаной), but it doesn't know that mice is the plural of mouse. - No typo tolerance.
sourdoguhfinds nothing. - No relevance magic. The score is simple and predictable — title, frequency, recency — and we prefer it that way.
What you gain
Search results are always exactly what's on disk right now. There's nothing to rebuild, nothing to corrupt, and the whole search is about 250 lines of Go that you can read in ten minutes (search.go in the source archive).