Under the Hood of Vector Databases

You've probably heard about 'embeddings', 'vectors' , 'RAG', they're everywhere.

Recommendation systems that surface eerily relevant content, chatbots that can retrieve info from massive document collections. All reply on the same thing: finding things that are 'similar' to other things.

Traditional databases are great at exact and filtered queries like:

• give me the details of the order with id 242.
• all the comments since last week.

but ask them, "What was Macbeth told by the witches?", and nothing works. This is where vector databases come in.

In this article, we will cover what vector databases are, how they work under the hood and the algorithms that the 'similarity' search fast.

What are Vectors?

A vector (or embedding) is just an array of numbers that represent something.

That "something" could be a word, a sentence, an image, a user, a product, or really anything you can feed into a machine learning model. The magic here is that 'similar' things end up with 'similar' vectors.

The typical embedding has somewhere between 128 and 1535 dimensions.
Some models like text-embedding-3-large from OpenAI use 3072.

Each dimension captures some aspect of the meaning, though the individual dimensions are not usually interpretable by humans. What matters is that the geometric relationships between vectors reflect semantic relationships between the things they represent.

A thought on 'similarity'

If you're a keen reader, you must have noticed that so far in this article, I've been double quoting the word "similarity". Here's why:

Similarity is not a property of things; it's a relationship between things and a question. A plum and an apricot are similar if the question is "what's a good snack?" A plum and a pocket knife are similar if the question is "what fits in my pocket?" Neither answer is wrong, the context decides which aspects get to count. And human similarity judgments are stranger still: they're asymmetric.

In Amos Tversky's classic 1977 paper Features of Similarity, 66 participants picked "North Korea is similar to Red China" as the natural comparison, and only 3 picked "Red China is similar to North Korea".

This shows that we measure the less prominent thing against the more prominent one.

Geometry can't do that; any distance worth the name satisfies
d(a, b) = d(b, a), always.So when a vector database tells you two vectors are "similar", it is making a much narrower claim than the English word suggests.

It means: these items appeared in similar contexts in the training data, so the model placed them near each other under one fixed, learned weighting of aspects. That captures relatedness, often beautifully, but it will also happily place "coffee" next to "mug" and "Batman" next to "Joker". None of those are similar things; they're just entangled.

The geometry remembers association, not likeness.This is why the same query can feel right in one app and wrong in another.

The practical move is to stop guessing whether your embeddings capture the right notion of "similar" and to measure it with an eval set of queries and human-blessed good results.

Similarity Metrics

Once you have vectors, you need a way to measure how similar two vectors are. There are a few common approaches to this:

• Euclidean distance (L2) — the straight-line distance between two points in a straight line or place, yes, the one you learned in school. Smaller means more similar. Euclidean distance accounts for both direction and magnitude, so a long vector and a short vector pointing the same way are still "far".
  

• Cosine similarity — it measures how similar two vectors are by calculating the cosine of the angle between them. It ignores vector magnitude and focuses purely on orientation, yielding a score from -1 (opposite) to 1 (identical), with 0 meaning orthogonal or unrelated. This is the default for most text embedding models, where direction carries the meaning and length mostly reflects document length or confidence.
  

• Dot product (inner product) — The dot product is an algebraic operation that multiplies two equal-length sequences of numbers (usually vectors) to produce a single real number (scalar). It measures how much two vectors point in the same direction.
  
  

• Hamming distance — it is the number of places where two text strings or binary sequences of equal length do not match. For example, the strings "karolin" and "kathrin" have a Hamming distance of 3 because three letters differ.

The Search Problem: Nearest Neighbors

When we start to ask questions, our questions are usually framed in terms of a "query vector" which you can think of like your search term. A query vector is the embedding of the item to which you're trying to find similar things.

The K-Nearest Neighbors (KNN) problem is: given a query vector, give me the K most similar vectors in your collection. Or given an item, find the K most similar items in your collection.

This is exact KNN and it's effectively O(n) where n is the number of vectors (k is typically very small, so we can ignore it).

In Python pseudocode, it looks something like this:

def knn(query_vector, all_vectors, k):
    heap = []  # min-heap by similarity
    
    for vector in all_vectors:
        similarity = compute_similarity(query_vector, vector)
        if len(heap) < k:
            heapq.heappush(heap, (similarity, vector.id))
        elif similarity > heap[0][0]:
            heapq.heapreplace(heap, (similarity, vector.id))
    
    return sorted(heap, reverse=True)

For a million vectors with 1536 dimensions, that's ~6 billion floating point operations per query. This can get expensive and is too slow for many applications.

But what if we don't need to find the exact nearest neighbors? What if we're okay with finding vectors that are probably the nearest neighbors most of the time? This is Approximate Nearest Neighbor (ANN) search, and it's the foundation of every practical vector database. With ANN, we trade off accuracy for speed. We don't always find the exact nearest neighbors, but we find a lot of close ones quickly.

The key metric for ANN quality is recall. Recall means out of all the actual positive cases, how many did the model find?

In our case it translates to: of the true top-K nearest neighbors, what fraction did we actually find? A recall of 0.95 means we found 95% of the true nearest neighbors. For most applications, that's plenty good enough.

And this forms the underpinning of all vector databases. Vector databases allow you to make a smooth tradeoff between these three things:

• Recall: How accurate are our results?
• Latency: How fast can we return results?
• Memory: How much space does our index consume (especially RAM)?

How Vector Databases Work?

So we've got vectors, we've got similarity metrics, and we know that brute-force search doesn't scale. How do vector databases actually make this fast? It comes down to clever data structures that let us skip most of the comparisons. We'll look at the indexing algorithms that power approximate nearest neighbor search, then cover the practical concerns: filtering, updates, and scaling to billions of vectors.

Indexing Strategies

The key to making a vector database work is computing indexes on the vectors you have stored. These indexes make the retrieval faster and often require some tradeoffs as described above, often compromising recall for big reductions in latency. They also introduce complexity for inserts, updates, and deletion of vectors which we'll get into a bit. First, let's talk about some of the main indexing strategies.

A thing to note here is that there are a lot of indexing strategies that you can use, but without running actual experiments on your data, it's hard to reason about what's superior for your app.

In fact, this is one of the main benefits of using a vector database. It lets you swap indexing strategies and tune parameters without rewriting your application.

You typically have an evaluation set, which is basically queries with known good results, and measure recall and latency trade-offs to find what works best for your use case.

HNSW (Hierarchichal Navigable Small World)

HNSW is the most popular algorithm in production vector databases. If you remember one indexing strategy, make it this one.

The intuition is similar to skip lists. In a regular linked list, finding an element requires scanning through every node, it's O(n). Skip lists solve this by adding "shortcut" layers above the base list. The bottom layer has all elements, but higher layers skip over most elements, keeping only a random subset. To search, you start at the top express lane and zoom forward until you'd overshoot, then drop down a level and continue. This gets you O(log n) search in a linked list.

HNSW applies the same idea to graph-based nearest neighbor search. It builds a multi-layer graph where each node is a vector. But what does that actually mean?

Think of it this way: when you insert a vector into an HNSW index, it becomes a node. The index then finds the vectors most similar to your new vector and creates edges connecting them. So if you insert an embedding for "espresso", it gets connected to nearby embeddings like "americano" and "cappuccino", not because anyone manually linked them, but because their vectors are geometrically close in the embedding space.

The result is a graph where you can "walk" from any vector to similar vectors by following edges. And crucially, if two vectors are similar, there's likely a short path between them through the graph.

The same idea from skip lists appears here. The bottom layer (Layer 0) contains all vectors, each connected to their nearest neighbors. But searching this dense graph is still slow for large datasets.

Searching HNSW works by starting at the top and working down:

1. Start at the top layer with a random entry point
2. Greedy search: Move to whichever neighbor is closest to your query vector
3. Repeat until you can't get any closer at this layer
4. Drop down to the next layer (which has more nodes) and continue greedy search
5. At Layer 0, do a more thorough local search to find the K nearest neighbors

The top layers let you quickly zoom in to the right region of the space. By the time you reach Layer 0, you're already in the right neighborhood and only need to explore locally. This gives O(log n) search complexity with excellent recall.
HNSW consistently achieves 95%+ recall with low latency, which is why it has become the default choice.

But this isn't free. HNSW indexes are memory-hungry. You need to store the graph structure (all those edges) on top of the vectors themselves (roughly 2x) the memory of raw vectors.
Building the index is slow since you're constructing this elaborate graph structure. And inserts are relatively expensive because each new vector needs to find its place in the graph and establish connections at each layer. We'll get into this in a second.

IVF (Inverted File Index)

IVF takes a different approach. Instead of building a graph, it partitions your vectors into clusters using k-means clustering. Each cluster has a centroid which is the center point and vectors are assigned to their nearest centroid.

At query time, you first find the closest centroids to your query vector, then only search within those clusters. If you have 1000 clusters and search 10 of them, you've eliminated 99% of comparisons.

The parameter nprobe controls how many clusters you search. Higher nprobe means better recall but slower queries. This gives you a nice knob to tune the recall/latency tradeoff.

These probes are easily parallelized, so for a single query you don't necessarily need to take a latency hit as nprobe increases. But for real systems under load, you've got enough requests to saturate compute. This means a latency hit for the the average request.

IVF is faster to build than HNSW and handles inserts more gracefully as you just assign the new vector to a cluster. It uses less memory since you're only storing cluster assignments, not a full graph. The downside is typically lower recall for the same latency, especially if your data isn't clustered naturally.

Locality Sensitive Hashing (LSH)

LSH takes a fundamentally different approach. Instead of building a graph or clustering, it uses hash functions designed so that similar vectors are likely to hash to the same bucket. Regular hash functions try to avoid collisions. LSH hash functions are designed to cause collisions for similar items.

The most common approach for cosine similarity uses random hyperplanes.

Imagine drawing a random line through your vector space. Every vector is either "above" or "below" that line—that's one bit of your hash.
Do this with, say, 8 random hyperplanes and you get an 8-bit hash.
Vectors that are close together will likely be on the same side of most hyperplanes, so they'll have similar (or identical) hashes.

We make this more robust by using multiple hash tables with different random hyperplanes. A single table might miss similar vectors that happen to fall on opposite sides of one hyperplane. But with multiple tables, the probability that similar vectors share at least one bucket goes up dramatically.

At query time, you hash your query vector in all tables, collect all candidates from matching buckets, then compute exact distances only on this candidate set.

The tradeoff is clear: more tables and more bits means better recall but more memory and slower queries.

LSH was popular before HNSW became dominant. It's simple to implement, handles high dimensions well, and has nice theoretical guarantees. But in practice, HNSW usually achieves better recall for the same latency. LSH is still useful when you need:

• Very fast index building (just compute hashes)
• Streaming data where vectors arrive continuously
• Hamming distance similarity (LSH is natural here)

Annoy (yes, that's what it's called)

Like LSH, the idea of cutting up the vector space using random hyperplanes can be extended to tree-based structures.

Annoy (Approximate Nearest Neighbors Oh Yeah, from Spotify) builds a forest of random projection trees.

The idea is beautifully simple: recursively split your vector space with random hyperplanes until each leaf node contains a small number of vectors.

To build a tree, you pick two random vectors and draw a hyperplane equidistant between them. All vectors on one side go into the left subtree, all vectors on the other side go into the right subtree. Repeat recursively until each leaf has few enough vectors (say, 100). The result is a binary tree where nearby vectors tend to end up in the same leaf or nearby leaves.

To search, you traverse the tree toward the leaf that matches your query vector. But a single tree can make mistakes, so, your true nearest neighbor might have ended up on the other side of an early split. So Annoy builds a forest of many trees (typically 10-100), each with different random splits. At query time, you search all trees, collect candidate leaves, and compute exact distances on the union of candidates.

The killer feature of Annoy is memory mapping, Oh Yeah. The entire index is stored as a single file that can be mmap'd into memory. mmap is a low-level system call that maps a file into memory and it's very efficient compared to the alternative of orchestrating file reads and writes from userspace. This means:

• Multiple processes can share the same index without copying
• You can work with indexes larger than RAM.
• Index loading is instant (just mmap, no deserialization)

The downside is that Annoy indexes are immutable. Once built, you can't add or remove vectors, you have to rebuild the entire index.
This makes it great for static datasets (like Spotify's music catalog that updates in batches) but unsuitable for real-time applications where vectors arrive continuously.

Annoy was the go-to solution at many companies before HNSW took over. You'll still see it in production systems where the dataset is static and memory mapping is valuable

Filtering and Hybrid Search

Vector search opens up a way to retrieve "similar" items from a database, and we can make that efficient (albeit slightly inaccurate) using algorithms like HNSW, IVF, and LSH. But what about when we want to retrieve items that are not similar, but match a specific query?

Real applications rarely want "find the 10 most similar items" without constraints. You usually want "find the 10 most similar items that ship to the user's country" or "that are available in the user's size" or "that the user hasn't already saved".

This is called filtered vector search, and it can get trickier than it sounds. You have two options:

Post-filtering: Find the top-N similar vectors (where N >> K), then filter down to K results. The problem is if your filter is restrictive, you might not find K results. You can increase N, but then you're doing more work.
Pre-filtering: Filter first, then search only within the filtered set. The problem is you might not be able to use your fancy index structures on an arbitrary subset of data.

Most vector databases use hybrid approaches to take the heavy lifiting off your shoulders. Some maintain multiple indexes for common filter combinations. Others integrate filtering directly into the index traversal. Let's look at how three popular systems handle this:

• Postgres's pgvector relies on Postgres's query planner. You write a normal SQL query with both a WHERE clause and an ORDER BY using vector distance. The planner decides whether to use the vector index, a B-tree index on your filter column, or some combination. For highly selective filters, it often skips the vector index entirely and does brute-force similarity on the filtered rows, which is actually faster. The catch is that pgvector doesn't do true "filtered HNSW traversal". It's either/or, so you can get suboptimal plans when the filter selectivity is in an awkward middle ground.
• Elasticsearch has tighter integration. Its kNN search supports a filter parameter that applies during index traversal, not after. Under the hood, it uses a combination of HNSW and filtered candidate generation. When you search, ES first identifies candidate vectors from the HNSW graph, then applies your filter, then continues exploring until it has enough filtered results. This means highly restrictive filters slow down the search, but you're guaranteed K results if they exist. ES also supports hybrid search natively where you can combine BM25 keyword scoring with vector similarity using sub_searches or rescore.
• Finally, purpose-built vector databases like Pinecone treat metadata filtering as a first-class feature. Every vector can have arbitrary metadata (up to 40KB), and filters are applied during the ANN search, not before or after. Pinecone builds specialized index structures to support this by basically maintaining inverted indexes on metadata fields alongside the vector index. When you query with filters, it intersects the metadata filter results with the vector search in a single operation. Pinecone also lets you tune the "filter effort" parameter to trade off between filter precision and latency.
  

All to say, there're options.

Finally, to add even more complexity there's a class of searches where we want to do both full-text search and vector search at the same time, often called "hybrid search".

A query like "cozy mystery novel set in a bakery" might use keyword matching for "mystery" and "bakery" while using vector similarity to capture the "cozy" vibe, surfacing titles that never say the word but read the same way.
This often gives better results than either approach alone, and can be accomplished by doing both searches in parallel and merging the results, or by clever merging strategies

Inserts, Updates, and Index Maintenance

Vector databases are generally optimized for read-heavy workloads. Writes are more complicated, especially with sophisticated indexes like HNSW.

Inserts can work in real-time, but it's often compute-expensive to do so. Adding a new vector to an HNSW graph means finding its place and updating connections. And if you're doing many inserts, the graph structure can degrade over time. Similarly, with IVF over time you may need to rebuild the index as clusters move and evolve or risk performance degradation.

Many systems handle this by maintaining a small "hot" index for recent inserts and a larger "cold" index for older data. Queries search both and merge results. Periodically, the hot index gets merged into the cold index with a full rebuild. The "hot" index need not be a full index at all, it can also be just a dumb list of entries that haven't been indexed which we exhaustively search.

Updates are usually implemented as delete + insert. Most systems use soft deletes (marking vectors as deleted) rather than actually removing them from the index. This means deleted vectors still consume space and slow down queries until you rebuild or compact the index.

Index rebuilds can be slow. Building an HNSW index over millions of vectors can take hours. You need to plan for this. Some strategies:

• Rolling rebuilds.
• Partitioned indexes where you can rebuild one partition at a time.
• Background reindexing that doesn't block queries.

If your embeddings change frequently, you'll want to think carefully about your update strategy. Batch updates with periodic rebuilds are often more practical than real-time updates.

The expensive index maintenance is one major difference between vector databases and traditional databases. Traditional databases can usually handle updates in real-time because they're designed to be able to handle a lot of writes. Vector databases are oftentimes not. In interviews, this means you're thinking (and discussing) more deliberately about a rebuild strategy including things like a side "hot" index as discussed above.

Vector Database Options

When it comes to choosing a vector database, there's a lot of choices. The practical advice is to start simple.

TBH, you probably don't need a purpose-built vector database. Extensions to databases like Postgres and Elasticsearch are good enough to handle millions of vectors. Here's a practical guide on how you should go about your choice:

• pgvector is the first thing to try if you're already on PostgreSQL. It supports both HNSW and IVF indexes and handles millions of vectors without breaking a sweat. The real advantage is everything else you get for free: ACID transactions, familiar tooling, and the ability to join vector results with your relational data.
• Elasticsearch kNN is great if you already have Elasticsearch for search. Adding vector search is straightforward, and you get excellent hybrid search (keyword + vector) out of the box.
• Redis Vector Search fits well if you need real-time, low-latency requirements. Redis is already a common part of most architectures, and the vector extension is simple to use.
• S3 Vector is a relatively new offering from AWS that enables you to store vectors in S3 and query them using the S3 API. It's a good option if you're already using S3 for other purposes and don't want to add the complexity of a dedicated vector database.

Purpose-Built Vector DBs (When You Need Scale)

if you're dealing with real scale ( > 100m vectors) or just want to get fancy, you should consider a purpose-built vector database.

• Pinecone is fully managed and serverless. You don't run any infrastructure; you just call an API. It's the easiest to operate, which is worth a lot. The tradeoff is cost and less control.
• Weaviate is open source with good hybrid search support and a GraphQL API. It's a reasonable middle ground between DIY and fully managed. Easier to operate than some alternatives but still gives you control.
• Milvus is open source and built for serious scale. It can handle billions of vectors. The flip side is operational complexity. You're running a distributed system with multiple node types.
• Qdrant is open source, written in Rust, and has particularly good filtering support. Worth considering if complex filtered queries are central to your use case.
• Chroma is lightweight and great for prototyping. It's increasingly popular in the LLM/RAG space because it's easy to get started with.
• Hydra DB is yet another recent open source vector database. It's purpose-built for AI agents, using a graph-native architecture to map relationships and track entity evolution over time.

Architecture Patterns for Vector DBs

There are a few common ways to wire up vector search in a system:

• Vector DB as a separate service. This is the most common. Your application generates or retrieves an embedding, sends it to the vector service, gets back IDs of similar items, then fetches full item details from your primary database. Clean separation of concerns.
• Hybrid search. Query goes to both a keyword index (like Elasticsearch) and a vector index. Results get merged with some ranking function. Good for search applications where both exact matches and semantic similarity matter.
• Two-stage retrieval. Vector search returns a large candidate set (maybe top 1000), then a more sophisticated (but slower) model reranks them to pick the final results. Common in recommendation systems where the reranker can use features the embedding doesn't capture.

TLDR;

Vector databases enable a new class of applications built on semantic similarity rather than exact matching.

The core technology is approximate nearest neighbor search, with HNSW being the most common algorithm in production systems.

The practical advice is to start simple. If you're running PostgreSQL, try pgvector first. Only graduate to a purpose-built vector database when you've outgrown what extensions can provide.
The complexity of operating another system is often underestimated. The field is evolving fast. New indexing algorithms, tighter database integrations, and better tooling appear regularly. But the fundamentals of embedding data, measuring similarity, and making tradeoffs between recall, latency, and memory will remain relevant regardless of which specific technology wins.

That's it for this one folks!

If you got to learn something or liked this article, you can check out more of blogs here.

Please consider following me on LinkedIn and X.

Have a great day :)