Vector Index Structures

Exhaustive search compares a query to every vector — perfect recall, but O(N) work per query, hopeless at a billion vectors. Every vector index is one answer to the same question: impose a structure so a query only has to look at a slice of the data. They differ only in how they choose the slice.

Interactive Index Structure Visualization

The explorer below is real: it partitions genuine GloVe vectors with k-means into cells, routes a query to its nearest cells, and measures recall@10 against an exhaustive scan — and the fraction of the corpus it had to touch. The nprobe knob is the universal speed/accuracy dial.

The families of index

Three structural ideas cover almost every production vector index:

Inverted file (IVF). Cluster the vectors (k-means) into cells and keep, per cell, the list of vectors it owns. A query scores the nprobe nearest centroids and scans only those cells. Build is one k-means; query is a partial scan. This is the structure in the explorer, and the base layer of IVF-PQ.

Trees. Recursively split space into nested regions — KD-trees on axis-aligned cuts, ball/VP-trees on metric balls. Search descends to the query's leaf and back-tracks. Elegant in low dimensions, but the curse of dimensionality makes back-tracking visit most of the tree once d is large, so trees fade out for high-dimensional embeddings.

Graphs. Connect each vector to a few near neighbors and search by greedy walk — start anywhere, hop to the neighbor closest to the query, repeat. Graph indexes like HNSW dominate modern benchmarks because a walk reaches the answer in a logarithmic number of hops regardless of dimension.

The IVF case is just a k-means plus a partial scan — the whole index in a dozen lines:

def build_ivf(X, n_cells):
    centroids = KMeans(n_cells).fit(X).cluster_centers_
    cell_of = nearest(X, centroids)                  # vector → cell id
    cells = [np.where(cell_of == c)[0] for c in range(n_cells)]
    return centroids, cells

def search(q, centroids, cells, X, nprobe, k=10):
    probe = np.argsort(((centroids - q) ** 2).sum(1))[:nprobe]  # nearest cells
    cand = np.concatenate([cells[c] for c in probe])            # scan only those
    return cand[np.argsort(-X[cand] @ q)[:k]]

The one knob they share

Every approximate index exposes a dial between recall and work. For IVF it is nprobe — the number of cells scanned. Recall is the overlap with the true neighbors; cost is the fraction of vectors compared:

Turn the knob up and you approach exhaustive search (recall → 1, work → N); turn it down and you trade a little recall for a large speedup. The whole craft of ANN is finding indexes whose curve hugs the top-left corner — high recall for little work.

Choosing a structure

Trees still win for low-dimensional or exact metric search; for high-dimensional embeddings the real choice is IVF (cheap, memory-light, pairs with PQ) versus HNSW (fastest at high recall, heavier to build and store). Most vector databases ship both.

Best practices

1. Right-size the partition. A common IVF rule of thumb is n_\text{cells} ≈ √(N), then tune nprobe against a recall target.
2. Measure recall, not just latency. An index that is fast but recalls 60% is the wrong default — plot the recall/work curve and pick a point on it deliberately.
3. Layer compression on top. The partition decides what to scan; quantization decides how cheaply each comparison runs. Production indexes do both.
4. Skip indexing below ~10k vectors. A flat scan is simpler and often faster than maintaining an approximate index at small scale.

References

• Jégou et al. "Product Quantization for Nearest Neighbor Search" (IVF-ADC)
• Malkov & Yashunin "Efficient and robust approximate nearest neighbor search using HNSW"
• Bentley "Multidimensional Binary Search Trees" (KD-trees)

Related concepts