Indexing in vector databases
Without an index, finding the nearest vector means comparing the query against every stored vector — linear in the corpus and hopeless past a few hundred thousand. An index organises the vectors so most of them are never examined, and pays for that with recall: it may miss a true neighbour.
Overview
Why exact search stops working
A flat index stores the vectors and compares the query with every one. It is exact, trivially correct, and the right answer for small collections — and the cost is O(n·d) per query, so a million 768-dimensional vectors is around 768 million multiply-adds for a single search.
It is also the ground truth. To measure any approximate index's recall you need the true neighbours, and a flat search over a sample is how you get them.
Parameters
Visualisation
—Readout
What to watch
- Exact search touches every vector; the cost is linear in the corpus.
- An index skips most of them, and can miss a true neighbour.
- Recall, latency and memory — pick two.
Indexing in vector databases: A Practical Guide
What does a vector database index actually do, and why can't it just compare every vector?
What an index buys and what it costs
Every approximate index prunes: it organises vectors so that most can be skipped without being compared. That turns a linear scan into something closer to logarithmic, and introduces the possibility of missing a genuine neighbour because the structure routed the search elsewhere.
So the metric is recall@k: of the k true nearest neighbours, how many did the index return? 0.95 is typical and usually fine for RAG, where a reranker sees the top 50 anyway. It is not fine for deduplication or exact matching.
The families, briefly
IVF clusters the vectors and searches only the nearest few clusters. Cheap to build, and it misses neighbours that sit just across a cluster boundary.
HNSW builds a navigable small-world graph and walks it greedily. Best recall-for-latency, and the highest memory — it stores the graph as well as the vectors. This is the default in most vector databases; see ANN indexing.
Product quantization compresses each vector into a short code, cutting memory by an order of magnitude at some cost to recall. Usually combined with IVF rather than used alone.
Also note what an index does not do: filtering by metadata is a separate problem, and combining it with vector search is where most vector databases differ from each other — see permission filtering.
Things to try
- Set clusters probed to 1. Recall collapses — most true neighbours live in clusters the search never opened.
- Raise probes until recall reaches 1.0. You are now comparing against the whole corpus: an exact search with extra steps.
- Raise clusters with probes fixed. Finer clusters mean fewer comparisons and lower recall — the same trade from the other direction.
What to remember
Without an index, finding the nearest vector means comparing against every stored vector. An index prunes most of them and pays for it in recall, so the metric is recall@k measured against an exact search. Recall, latency and memory are the three knobs, and every index type exposes them under different names.