In-memory inverted-index full-text search

Definition

This is the data structure you use when, like a blog·document search box, you want to quickly pull "the list of posts containing this word." If you build a table in advance of "which word appears in which documents," then at search time you don't scan every document — you just look at that table.

Unpacking the terms: a token is a piece a document is split into as a search unit (usually one word), and an inverted index is a mapping in the direction "token → the list of documents containing that token." The original document is ordered "document → the words inside it"; this means flipping that around (inverted). Full-text search is the technique of building this inverted index in advance to process queries quickly, and in-memory search is loading that inverted index wholesale into process memory.

Why it's needed

Scanning the whole document each time to find a substring gets slow in proportion to the number of documents N and the query length, and you'd have to implement ranking·typo tolerance·prefix matching yourself. The inverted index moves this into a precomputed data structure, cutting the cost at search time. In environments where a resident search server is hard to run, you can load a pre-built index into memory and provide the same search quality more lightly.

How it works

1. Index stage: tokenize each document (split into words) and, per token, build a list of appearing document ids (posting list — the roster of documents where one token appears).
2. Query stage: tokenize the search terms the same way, and intersect/union each token's posting list to gather candidate documents.
3. Ranking: score and sort candidates by field weight (title > tags > body), TF (term frequency — how many times that word appears within one document), proximity (how close the search terms are to each other), etc.
4. prefix/fuzzy matching: absorb partial input and typos with prefix ("app" matches up to "apple") and fuzzy (edit-distance-based approximate matching — tolerating a few typo characters).

Practical application

// Pre-built index documents (id + searchable fields)
type Doc = { id: string; title: string; tags: string[]; body: string };

const index = buildIndex(docs, {
  fields: ["title", "tags", "body"],
  boost: { title: 3, tags: 2 }, // field weights
  prefix: true,
  fuzzy: 0.2,
});

const hits = index.search(query, { limit: 12 });

Fix the index as a build artifact to eliminate runtime generation cost, and reuse it as a singleton on warm instances.

Trade-offs

The in-memory library type is lightweight and simple to deploy without external hosting, but as the number of documents grows, memory·load time increase and it's weak at advanced processing like CJK morphological analysis. A resident search engine is strong at per-language pipelines·large scale·incremental updates but costs a separate process·hosting.

When not to use

If hundreds of thousands to millions of documents, complex filters·facets·per-language morphology quality are central, the in-memory library type is unsuitable. Use a resident search engine then. Also, if you must incrementally index frequently changing documents in real time, a build-time fixed index doesn't fit.

Common mistakes

• Indexing CJK text with a whitespace-based tokenizer, dropping Korean search quality.
• Weighting all fields equally, so a title match is buried by a body match.
• Rebuilding the index on every request, inflating cold start·latency (not using a singleton).

Related concepts

• serverless-stateless-execution — the background for using a library-type index inside a function when you can't run a resident engine.