Finding the Needle in a Haystack
With your vectors stored, the core operation of a vector database is nearest neighbor search: given a query vector, find the K stored vectors that are most similar to it.
The brute-force approach is exact k-Nearest Neighbors (k-NN): compute the distance between the query vector and every single stored vector, then return the K smallest distances. This is perfectly accurate but scales as O(n × d), where n is the number of vectors and d is the number of dimensions. At one million vectors with 1,536 dimensions each, a single query requires over 1.5 billion floating-point operations. At one billion vectors, it becomes completely impractical — queries would take seconds or minutes.
To make search fast at scale, vector databases use Approximate Nearest Neighbor (ANN) algorithms. These algorithms build intelligent indexes — data structures that organize vectors so that only a small fraction of them need to be examined per query. The trade-off is a small reduction in recall (you might retrieve the 2nd-closest match instead of the absolute 1st), but in practice the accuracy loss is negligible (typically >95% recall) while query latency drops from seconds to milliseconds.
The two most important ANN indexing algorithms are IVF and HNSW.