As AI systems become more complex, traditional databases struggle to efficiently handle high-dimensional data like embeddings. This is where Vector Databases come in, designed specifically for similarity searches across N-dimensional vectors. But how do we actually perform efficient searches in such systems?

⚠️ Why Traditional Indexing Fails

In traditional relational or NoSQL databases, searches rely on sorted columns and use binary search for range or point queries, giving a time complexity of O(logN).

However, in vector databases, we’re dealing with vectors like [1, 4, 6, 8, ...], which can have hundreds of dimensions. Sorting across all dimensions simultaneously is not possible. so traditional indexing falls short.

🧠 How Vector DB’s Search: It’s About Distance, Not Columns

Unlike traditional DBs, vector DBs don’t look for an exact match in one column, they perform similarity searches based on distance metrics (like Euclidean or cosine similarity) between vectors.

For example, if your search vector is [7, 7, 8, 4, ...], the system returns the most similar vectors, not just exact matches. wherein with vector databases it won’t work since each vector has N dimensions. No way to sort all N dimensions together.

Incoming query is based upon overall distance, not distance with just one column.

🗺️ Enter Spatial Algorithms

To narrow down the search efficiently, one approach is to map vectors into space:

One way is to do with take all the 2D vectors and plot them on X-axis and Y-axis, then when we get an search query: [7,7,8,4,…] we can map it to the two-dimensional space and find the nearest vector using a quad tree.

A quad tree basically splits 2D space into 4 regions recursively. So at root node we can decide which direction to go to, whether top-left, top-right, bottom right, bottom right, then we can take the resultant area and then again split it into 4 more regions.

📦 Quad Tree (for 2D vectors) - key takeways

We can treat two values of a vector as X and Y coordinates.
The search space is recursively divided into four quadrants (top-left, top-right, bottom-left, bottom-right).
We continue narrowing the region until we reach the nearest match.

But real-world vectors are N-dimensional, so quad trees don’t scale.

This operation narrowes search space till we are just left with one vector, which inturn will be the nearest vector for this search query. So this algorithm will work for 2D space but because we have N dimensional space, we need a variation of quad tree which works on any number of dimensions not just 2D.

We can do that using k-D tree, which allows search queries in 2D space

k-D Tree :

Main idea is similar to quad tree,

we first take input search vector and first go to root node, here we use one random dimension to split tree.

Assume, we take less value of first dimension vector, where all dimensions of values less then that are on LHS and greater then are on RHS, since our search vector, lets suppose eg - search vector : (7, 0, 5) has value 7 initially we go towards right.

In next level we may have different dimension, since we have value of 0 we go on LHS.

We keep going down the tree till we meet cluster of vectors to do a brute force search.

The closest of those vectors will be nearest neighbour match.

🌲 k-D Tree: Multi-Dimensional Spatial Search

A k-D Tree extends the quad tree idea to multiple dimensions: key takeways.

It recursively splits the data across different dimensions.
For each level, a new dimension is chosen to split the space.
For example, with a search vector [7, 0, 5]:
- At level 1 (dim 0), compare 7 and decide to go right.
- At level 2 (dim 1), compare 0 and go left.
- Continue until you reach a small cluster for brute-force comparison.

This method works well up to 20–30 dimensions, but beyond that, it runs into limitations.

Ideally KD-tree should work in vector database, but it has some drawbacks,

It does a lot of branching taking lot of space.
It doesn’t give good results, not very accurate, the root is very heavily branching and when we traverse to independent clusters, they don’t work out too well.

What Works Better?

More efficient alternatives include:

HNSW (Hierarchical Navigable Small World) »» fast and accurate for high-dimensional spaces.
ANNoy (Approximate Nearest Neighbors) » developed by Spotify for large-scale recommendation systems.

We'll cover these in future posts.

Thank you for reading.
If you're building AI systems, understanding vector DB search algorithms is a superpower ⚡

🔍 How To Search in Vector Databases While Building AI Systems?