Vector Indexing Methods

An index is a data structure that makes vector search fast. Without an index, finding similar vectors requires comparing your query against every single stored vector — which becomes impossibly slow at scale. This topic explains how indexes solve that problem.

The Telephone Book Problem

Imagine looking up a phone number in an unsorted list of 10 million names. You must read every entry. A telephone book solves this by sorting names alphabetically, so you jump directly to the right section.

Vector indexes solve a harder problem: data is not sorted alphabetically — it exists in hundreds of dimensions. Index methods use clever geometric and graph-based tricks to navigate that high-dimensional space quickly.

Brute Force: The Baseline

Before indexes, understand the naive approach:

BRUTE FORCE (Flat Index / KNN)
─────────────────────────────────────────────────
Query vector arrives
  ↓
Compare against Vector 1 → distance = 0.82
Compare against Vector 2 → distance = 0.34  ← keep
Compare against Vector 3 → distance = 0.91
...
Compare against Vector 1,000,000 → done

Time: O(n × d)  where n=vectors, d=dimensions
Result: 100% accurate, very slow for large n

Brute force works fine for datasets under ~100,000 vectors. Beyond that, you need an index.

The Four Major Index Types

1. Flat Index

Stores all vectors as-is and searches exhaustively. 100% accurate. Used for small datasets or as a benchmark to measure other indexes against.

2. IVF — Inverted File Index

Divides the vector space into clusters (like neighborhoods on a map). At search time, it only checks clusters near the query instead of all vectors. Much faster than flat search, with slight accuracy loss.

IVF STRUCTURE:
─────────────────────────────────────────────
Vector Space divided into 100 clusters:

  Cluster 1  ●●●●●   Cluster 2  ●●●●
  Cluster 3  ●●●     Cluster 4  ●●●●●●
  ...

Query arrives → find nearest 3 clusters → search only those
Skip 97 clusters entirely → 97% less work

3. HNSW — Hierarchical Navigable Small World

Builds a multi-layer graph where vectors connect to their nearest neighbors. Search starts at the top (sparse, fast navigation) and drills down to the bottom (dense, precise results). This is the most popular index in production systems today.

4. PQ — Product Quantization

Compresses vectors into shorter codes to save memory. Searches compressed codes instead of full vectors. Trades some accuracy for massive memory savings — useful when storing billions of vectors.

Index Comparison at a Glance

The Accuracy vs. Speed Trade-off

Every ANN index accepts a trade-off between accuracy (recall) and speed. You tune this trade-off with index parameters.

RECALL-SPEED CURVE:

Accuracy (Recall)
100% │●  Flat Index (exact)
     │
 99% │         ●  HNSW (high settings)
     │
 96% │                   ●  HNSW (default settings)
     │
 90% │                              ●  IVF + PQ
     │
     └──────────────────────────────────────── Speed
          Slow              Fast          Very Fast

Increasing recall (accuracy) always costs speed. Reducing recall gains speed. Most production applications target 95–99% recall — losing 1–5% of perfect results in exchange for millisecond response times is an acceptable trade-off.

How to Choose an Index

How many vectors do you have?
  │
  ├─ Under 100K → Use FLAT INDEX (simplest, exact)
  │
  ├─ 100K – 10M → Use HNSW (fast, accurate, widely supported)
  │
  └─ Over 10M → Use IVF + PQ or HNSW with compression

Is memory a major constraint?
  │
  └─ YES → Add Product Quantization (PQ) to compress vectors

Index Build Time vs. Query Time

Building an index takes time upfront, but pays off at query time. A flat index builds instantly but searches slowly. HNSW takes minutes or hours to build for large datasets, but then searches in under 10 milliseconds.

Plan your indexing strategy before you store data. Changing an index type on a large dataset requires rebuilding from scratch, which can take hours in production systems.