The most common (and most costly) operation of the marginalia search engine’s index is something like given a set of documents containing one keyword, find each documents containing another keyword. The naive approach is to just iterate over each document identifier in the first set and do a membership test in the b-tree containing the second. This is an O(m log n)-operation, which on paper is pretty fast. It turns out it can be made faster.
