Approximate search, the big picture
Every approximate nearest-neighbour (ANN) index answers the same question: how can we find the closest vectors without comparing against all of them? The answer is always some form of organising the vectors ahead of time so a search can jump straight to the promising region.
An everyday analogy
Finding the nearest coffee shop in a city:
- Brute force: measure the distance to every coffee shop in the city. Exact, slow.
- Clustering (IVF): first pick your neighbourhood, then only check shops in it — and maybe the next neighbourhood over. Fast, occasionally misses a shop just across the border.
- Graph (HNSW): ask a well-connected local, who points you to someone who knows your street better, who points you to the shop. Fast, follows a chain of "closer and closer" hops.
- Compression (quantization): keep a rough sketch of every shop's location instead of exact GPS coordinates, so the whole map fits in your pocket.
Real systems combine these ideas.
The three-way trade-off
Every index setting moves you along three dimensions:
| Goal | What it means | How you usually pay for it |
|---|---|---|
| Recall (accuracy) | Finding the true nearest neighbours | More work per query, or more memory |
| Latency / throughput | Fast queries, many per second | Lower recall, or more memory |
| Memory / cost | Fitting the index in RAM cheaply | Lower recall, or slower queries |
You can usually have two of the three cheaply. Tuning a vector database means picking the point on this triangle that suits your product.
There is no "best" index — only the best index for your data size, recall target, latency budget and hardware budget.
The main index families
| Family | Core idea | Well-known examples |
|---|---|---|
| Graph-based | Connect each vector to its near neighbours; search by walking the graph | HNSW, DiskANN (Vamana) |
| Clustering / partitioning | Group vectors into clusters; search only the nearest clusters | IVF |
| Quantization | Compress vectors so more fit in memory and comparisons are cheaper | Scalar, product and binary quantization |
| Hashing | Hash similar vectors into the same buckets | Locality-sensitive hashing (LSH) |
| Tree-based | Recursively split space into regions | Annoy (random projection trees), KD-trees |
Graph-based HNSW is the default in most modern vector databases, so it gets the next chapter. IVF and quantization follow, because they matter most at large scale.
Build time vs query time
Indexes shift work from query time to build time. Building an HNSW graph or training IVF clusters takes time and CPU, so:
- Bulk-loading large datasets can take minutes to hours.
- Some indexes (IVF, product quantization) need a representative training sample before they can be built.
- Index parameters chosen at build time can only be changed by rebuilding.
Search-time knobs
Most indexes also expose a query-time setting that trades speed for recall without rebuilding — efSearch in HNSW, nprobe in IVF. This is the single most useful tuning lever you have, and we come back to it in Performance tuning.
When evaluating an index, never look at speed alone. Always report speed at a given recall — "2 ms at recall@10 = 0.95" — otherwise comparisons are meaningless.
Senior Full-Stack Engineer · AI & AWS. I build production search, RAG and AI systems on AWS and Postgres.