Inside Vector Databases: IVF, Trees, HNSW and Product Quantization

Terms like RAG, vector databases, retrieval and chunking get thrown around constantly, and they sound heavier than they are. This piece starts with vector databases: what they store and how search inside them actually works.

Where the vectors come from

Embedding models, trained on enormous text collections, turn the meaning of a sentence into a list of numbers. Some are hosted, such as OpenAI's text embeddings and Google's Gemini embedding models. Others run locally, such as the Qwen3 embedding family in 8B, 4B and 0.6B sizes, or Jina's v5 text-small model with about 677M parameters. Pass your text through one of them and the result is a vector you can store and fetch later.

The vocabulary

A handful of terms recur in every vector database:

• Collection. A namespace holding points that share one fixed dimensionality and one distance metric.
• Point. A vector together with its ID and a payload of metadata.
• Distance metric. The way closeness is measured, usually cosine similarity, dot product or Euclidean distance.
• Upsert. The operation that puts data in, inserting new points and updating existing ones.
• Search. The query operation that everything else exists to serve.

The intuition: exact versus approximate

The naive way to find the vectors related to a query among 10,000 or more is to compute cosine similarity against every stored vector and keep the top k. The result is the set of exact nearest neighbors. At millions of vectors, though, that brute-force scan stops being practical for memory and time. So systems switched to approximate nearest neighbor (ANN) search, which accepts a small loss of accuracy in exchange for a large gain in speed.

That trade can be made in two broad ways. Indexing reduces how many comparisons are needed. Quantization reduces what each comparison costs. Together they make up the ANN toolbox.

Indexing, option one: clustering with IVF

An inverted file index (IVF) divides the vectors into clusters, each with a centroid. A query is first compared against the centroids only. Once the nearest cluster is found, the query is compared against the vectors in that cluster alone, and the best k of those come back.

The weaknesses are worth knowing:

• Neighbors near cell borders get missed. If the true match lives in a cell that wasn't examined, it's never found. Checking more cells helps, but slows the search and undermines the purpose.
• Quality decays as data changes. Clusters are fixed at build time, so new data keeps landing in old cells, and search quality drifts downward. Periodic rebuilds are required.
• Uneven clusters make speed unpredictable. Some cells grow huge while others stay tiny, so a query that lands in a big cell is slow and one that lands in a small cell is fast.
• It needs training data up front. The index can't be built until enough data exists to form meaningful clusters, which is awkward for applications that start from nothing.
• Two settings are hard to tune. The number of clusters and the number searched per query both affect results, and wrong values make search slow or inaccurate.
• High dimensions blur the clusters. With very long vectors, clusters get fuzzy, so accuracy per unit of work falls behind HNSW.

In a sentence: IVF is simple and saves memory, but it loses accuracy near boundaries and dislikes frequent updates, which is why it shines at billion scale when paired with product quantization while HNSW wins for live, high-accuracy search.

Indexing, option two: tree-based partitioning

Tree-based indexing borrows the idea of binary search. Rather than comparing the query to every vector, the space is repeatedly cut in half, and only the half containing the query is examined.

To build the index, take the whole space and split it with a dividing line, then split each half again, continuing until each small region holds just a few vectors. Each region is a leaf. In two dimensions the first split might cut along the x-axis, the next along the y-axis, and so on. All the splits form a binary tree in which each node is a yes or no question, such as whether x is below 5, and the leaves sit at the bottom.

When a query arrives, you start at the root and answer one question at a time: left of this split or right? Each answer discards half of the remaining space. After about log n questions, roughly 20 for a million vectors, you reach one small leaf and compare the query with the handful of vectors inside it.

There's a catch. The true nearest neighbor might lie just across a dividing line, close in distance but in another leaf, and a single tree would never see it. Libraries such as Spotify's Annoy therefore build many trees, each with different random splits. Every tree proposes candidates, the proposals are merged and the best are returned. What one tree overlooks, another usually catches.

The drawbacks:

• The boundary problem is worse than in IVF. With IVF, a boundary miss means checking one more cell. In a tree, a wrong turn near the top sends the search to a completely different region.
• The fix costs memory and speed. A forest of 50 trees means storing the index 50 times and searching 50 times per query, which buys accuracy with resources.
• Long vectors defeat it. Trees work well in 2D, 3D, maps and games. Modern embeddings have hundreds or thousands of dimensions, where a split line separates almost nothing meaningfully, since points on opposite sides can be nearly equidistant. That's the main reason the method fell out of favor for embedding search.
• The index is static. Trees are built once from existing data and can't cleanly accept new vectors. Annoy, for instance, needs a full rebuild to add data, which suits changing collections badly.
• It's generally outclassed. At equal accuracy, HNSW is faster, and at equal memory, IVF with product quantization scales further. Trees remain mostly in legacy systems and where small, memory-mappable index files matter.

In short, trees are simple and quick to build, but high-dimensional embeddings dissolve their splits and they can't take updates, so today they're mostly a stepping stone for explanation and not a production choice.

Indexing, option three: HNSW

Hierarchical Navigable Small Worlds, or HNSW, is the technique behind most vector databases. It organizes vectors as a graph with several layers. The top layers hold only a few vectors with long-range links, like highways between cities, and the lower layers hold progressively more vectors with shorter links, down to the bottom layer that contains every vector.

A search enters at the top and moves greedily to whichever neighbor is closest to the query. When no neighbor is closer, it drops one layer and repeats from that spot, with finer-grained links. At the bottom layer, it explores a wider neighborhood and returns the best matches. Long jumps cover distance quickly and short hops refine the answer, which is why the number of comparisons stays small even for huge collections.

A few parameters control the balance of speed and accuracy:

• M sets how many links each vector keeps. More links improve accuracy and recall but cost memory.
• efConstruction sets how wide the candidate search is while the graph is being built. Higher values give a better graph and a slower build.
• efSearch sets how wide the candidate list is at query time. Raising it increases accuracy and latency together.

Seeing how a query moves through the layers, and how these settings shape the path, explains how changing them alters search behavior.

Quantization: making each comparison cheaper

Indexing cuts the number of comparisons. Quantization shrinks the cost of each one. A single 1536-dimension vector of 32-bit floats occupies 1536 times 4, or 6144 bytes. For a billion vectors, that means terabytes of storage, far more than fits in RAM.

Product quantization

Product quantization chops each big vector into smaller segments of equal size. A 16-dimension vector might become, say, four segments of four dimensions. For each segment position, a codebook is trained on the stored data with 256 entries, each representing a typical sub-vector. Every segment is then replaced by the number of its closest codebook entry, which needs just one byte.

So a vector that took thousands of bytes becomes a short string of small integers. To search, the query is split in the same way, and distances to the codebook entries are computed once and reused through lookups for every stored vector. The computation is highly approximate, but the speedup and memory savings are large.

Choosing among them

A quick comparison sums things up:

• IVF is simple and memory-friendly. Pair it with product quantization for very large static collections.
• Trees are easy to understand and cheap to build, but suit low dimensions and unchanging data.
• HNSW gives high accuracy and fast live search, at the price of more memory.
• Product quantization compresses vectors and speeds up distance computations, with a controlled loss of precision, and combines with the indexes above.

Knowing these trade-offs helps you decide when approximate search is appropriate, which algorithm fits a workload, and when brute force is still the right answer, such as with small collections where exactness is cheap.