My Understanding of Indexes in Vector Databases: Flat Index, ANN, HNSW, HFresh

ChatGPT

While creating my RAG playlist on my YouTube “Praveen Reddy Learnings”, I came to a topic: Indexing in Vector Databases.

As I started preparing for it, I realised that I had never actually wrote a blog dedicated to vector indexes, which is why I decided to write this blog.

We need to understand, how does a Vector Database search through millions of vectors so quickly? That’s where indexes come in. So in this blog, let’s start from the basics, understand why indexes are needed in Vector Databases, explore the different indexing techniques available, and then dive deep into the most popular one used today: HNSW.

Indexes

How does a Vector Database find the most similar vectors so quickly?

Imagine we have only 100 vectors stored in your database. When a user asks a question, the user query is first converted into an embedding, and the database can simply compare the user query vector against all 100 vectors to find the most similar matches(using cosine similarity or so…).

Here it is a small dataset so, it is fine but, what happens when the dataset grows? What if we have 10 Million vectors ?

For every user query, the database would need to compare the user query vector against 10 Million vectors stored in the vector DB. This approach is known as Brute Force Search.

The major drawback here is: Speed.

As the number of vectors increases, the number of similarity calculations also increases. What works well for hundreds of vectors quickly becomes impractical when dealing with millions or even billions of vectors. The search latency starts increasing, computational costs go up, and the user experience suffers. This is exactly the problem that indexes are designed to solve.

Instead of checking every vector in the database, an index helps narrow down the search space and quickly guide the search toward regions where similar vectors are most likely to be found.

As we all know that, the concept of indexing is not new. We have been using indexes in traditional relational databases for decades. Imagine an employees table containing millions of records, and a user executes a query like:

SELECT *
FROM employees
WHERE employee_id = 1001;

Without an index, the database would have to scan every row in the table until it finds the matching employee. This process, known as a full table scan, becomes increasingly expensive as the table grows. To solve this problem, databases create indexes on frequently searched columns such as employee_id. Once an index is available, the database can directly navigate to the required records instead of searching through all rows, significantly reducing query execution time. Vector Databases face a very similar challenge. Instead of searching through millions of vector rows. Just as traditional databases use indexes to avoid scanning entire tables, Vector Databases use specialised vector indexes to avoid comparing a query against every stored vector, making similarity search fast and scalable.

Before we dive into the different types of vector indexes, below are the three key factors that every indexing algorithm is trying to optimise:

1. Search Speed

How quickly can the database return results?

2. Accuracy (Recall)

How close are the returned results to the actual nearest neighbours?

3. Memory Consumption

How much memory is required to store and maintain the index?

Now, let’s dive into some of the most commonly used indexing techniques in Vector Databases.

1. Flat Index (Brute Force)

The simplest indexing technique available in Vector Databases is the Flat Index, often referred to as Brute Force Search. Although it is called an index, it doesn’t perform any optimization. The vectors are simply stored as they are, and whenever a query arrives, the database compares the query vector against every single vector in the dataset. It calculates the similarity score for each vector, sorts the results, and returns the top matching vectors. In other words, nothing is skipped — every vector is examined before producing the final result.

2. Approximate Nearest Neighbour (ANN)

As datasets grew larger, researchers realised that most AI applications do not need the mathematically perfect nearest neighbour. For example, if the best match has a similarity score of 0.95 and another result scores 0.94, the difference is often negligible from a user’s perspective. This led to the concept of Approximate Nearest Neighbour (ANN), where the goal is to find results that are very close to the actual nearest neighbours while dramatically improving search speed.

IVF (Inverted File Index)

One of the earliest ANN techniques is IVF (Inverted File Index). Instead of searching every vector, first group similar vectors into clusters and then search only within the most relevant cluster.

IVF Working:

During index creation, vectors are grouped into multiple clusters, and a centroid is created for each cluster. When a query arrives, the database first finds the nearest centroid and then searches only the vectors belonging to that cluster.

ChatGPT

This significantly reduces the search space. Instead of comparing against one million vectors, the database may only need to examine a few thousand vectors within the selected cluster, resulting in much faster searches.

IVF Limitations:

The main limitation of IVF is that the actual nearest neighbor may exist in a different cluster than the one selected for the search. If that cluster is never examined, the best result can be missed, reducing recall, which is being handled in the next technique HNSW.

HNSW (Hierarchical Navigable Small World)

Now comes the most popular indexing technique used in modern Vector Databases: HNSW (Hierarchical Navigable Small World). The reason for its popularity is simple — it provides an excellent balance between search speed, recall, and scalability. Because of this balance, HNSW has become the default indexing choice for many production-grade vector databases.

In HNSW, every vector is represented as a node, and each node is connected to a set of nearby nodes. Together, these connections form a graph. When a query arrives, instead of comparing against every vector in the dataset, the algorithm navigates through this graph, hopping from node to node until it reaches the vectors most similar to the query.

ChatGPT

Instead of maintaining a single graph, HNSW organises the graph into multiple layers.

• Top Layer: Very sparse, containing only a few nodes that provide a rough starting point.
• Middle Layers: More nodes and connections, helping refine the search.
• Bottom Layer: Contains almost all vectors and performs the final fine-grained search.

A useful analogy is navigating with maps: You might first look at a country map to find the right region, then zoom into a state map, then a city map, and finally a street map. HNSW follows a similar approach, progressively narrowing down the search as it moves through the layers.

Because only a small portion of the graph is explored, HNSW can find highly relevant vectors without examining the entire dataset, making searches extremely efficient.

HNSW has become the industry standard because it offers an attractive combination of benefits:

• Extremely Fast Search: Only a small fraction of the dataset is explored during retrieval.
• High Recall: Often achieves recall rates above 95%, meaning it finds results very close to the true nearest neighbours.
• Excellent Scalability: Works efficiently even when the dataset contains millions of vectors.

HNSW Parameters

M:

The M parameter controls how many neighbours each node maintains in the graph.

Higher M

• Better graph connectivity
• Higher recall
• Increased memory usage

Lower M

• Lower memory consumption
• Faster index creation
• Reduced recall

efConstruction

The efConstruction parameter controls how much effort HNSW spends while building the graph. During index creation, HNSW evaluates multiple candidate nodes before deciding which neighbours should be connected.

Higher efConstruction:

• Better graph quality
• Higher recall
• Longer indexing time

Lower efConstruction:

• Faster index creation
• Lower graph quality
• Potentially lower recall

efSearch

The efSearch parameter is used during query time and determines how many candidate nodes are explored during the search.

Higher efSearch:

• Explores more nodes
• Better recall
• Slower search

Lower efSearch:

• Faster search
• Lower recall

A simple efSearch definition is:

How much effort should the database spend looking for the best possible answer?

The higher the value, the more effort it spends and the better the chances of finding the true nearest neighbors.

Dynamic Indexes

While HNSW works exceptionally well for large datasets, maintaining a graph structure for very small datasets may be unnecessary. To address this, some Vector Databases such as Weaviate introduced Dynamic Indexes.

The idea is simple:

For small datasets, the database uses a Flat Index because brute-force search is already fast enough. As the dataset grows, it automatically switches to HNSW to maintain high search performance. This approach avoids the overhead of maintaining an HNSW graph for tiny datasets while still providing scalability when the amount of data increases.

HFresh

While HNSW has become the most popular indexing technique, it comes with a tradeoff: the graph structure requires additional memory. As the number of vectors grows into the hundreds of millions or billions, maintaining a large graph can become expensive. To address this challenge, Weaviate introduced a newer indexing approach called HFresh.

Instead of building an HNSW graph for every vector in the dataset, HFresh first groups similar vectors into clusters. Rather than navigating through millions of individual vectors, it creates an HNSW graph only on the cluster centroids. During a search, the system first identifies the most relevant clusters and then searches within those clusters to find the final results.

This approach significantly reduces memory consumption because the graph is maintained on a much smaller set of centroids rather than on every vector. As a result, HFresh can scale more efficiently for extremely large datasets while still delivering good search performance.

For most RAG applications and medium-sized datasets, HNSW remains the most commonly used choice. However, for very large deployments where memory efficiency becomes a major concern, HFresh can be an attractive alternative.

So,

• Flat Index gives perfect accuracy but doesn’t scale.
• IVF introduced the idea of reducing the search space through clustering.
• HNSW took things further by organizing vectors into a hierarchical graph structure that allows extremely fast navigation while maintaining high recall.

That’s it all about Indexing in vector stores.

Thank You !!