# Build a Vector db from Scratch in c++

Vector databases are everywhere now.

Search, recommendation systems, retrieval-augmented generation (RAG), semantic similarity — almost every modern ML system quietly depends on fast nearest-neighbor search. And yet, for most of us, vector databases remain a black box. We use them, we tune a few parameters, but rarely stop to ask *why* they work the way they do — or *when* they stop working.

This project is my attempt to change that.

Instead of starting from a mature system or a clever approximation technique, I decided to rebuild a vector database **from first principles** in C++. The goal was not to compete with production-grade systems, but to understand the fundamentals: why certain designs work, where they break down, and what trade-offs they make between speed, accuracy, and complexity.

I start with the simplest possible baseline — an exact linear scan — and gradually layer in optimizations, SIMD instructions, multithreading, and tree-based indexing.

This blog documents that journey. It’s not a tutorial on “how to build the fastest vector database,” but a practical exploration of **how vector search behaves on real hardware** and **why modern systems are designed the way they are**.

If you want to dig deeper, experiment, or go through the full implementation, you can find the complete codebase here:  
👉 [**github.com/SriPrarabdha/vector\_db\_from\_scratch**](https://github.com/SriPrarabdha/vector_db_from_scratch)

# [Baseline Implementation (Linear Scan)](https://github.com/SriPrarabdha/vector_db_from_scratch)

Every optimization only makes sense if we clearly understand what we are optimizing **against**.  
So before touching SIMD, threads, or tree structures, the project starts with the most boring solution possible: **linear scan**.

Given a query vector, we compute its distance to **every single vector** in the database and then pick the top-k closest ones. That’s it. No shortcuts, no pruning, no approximation.

At first glance, this feels obviously inefficient. But linear scan has one extremely important property: **it is exact**. Whatever result it gives is the ground truth. Every faster method we build later will be judged relative to this.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1767419637129/cc53d077-09c3-4ca9-8d2f-b6f9d7ee6ea6.gif align="center")

### How linear scan is actually working here

Assume we have `N` vectors, each of dimension `D`. For a single query:

1. Take one stored vector.
    
2. Compute the distance to the query (L2 / Cosine distance).
    
3. Repeat for all `N` vectors.
    
4. Sort (or partially select) the closest `k`.
    

The time complexity is simple and brutal: **O(N × D)** per query.

```cpp
//square of euclidean distance
float l2_distance (const Vector& a, const Vector& b){
    assert (a.dim == b.dim);

    float sum = 0.0f;
    for(dim_t i = 0; i<a.dim ; ++i){
        float d = (a.data[i] - b.data[i]);

        sum += d*d;
    }

    return sum;
}

float cosine_distance(const Vector& a, const Vector& b){
    assert (a.dim == b.dim);

    float dot = 0.0f;
    float na = 0.0f;
    float nb = 0.0f;

    for(dim_t i = 0 ; i<a.dim ; ++i){
        dot += a.data[i] * b.data[i];
        na += a.data[i] * a.data[i];
        nb += b.data[i] * b.data[i];
    }

    if (na == 0.0f || nb == 0.0f) return 1.0f;

    return 1.0f - (dot / (sqrt(na) * sqrt(nb)));
}
```

Now let’s use this vanilla implementation of l2\_distance to implement our linear scan index. Refer [here](https://github.com/SriPrarabdha/vector_db_from_scratch/blob/59ad3202dae1420dc9149dcb2855147c72a9ece0/indexes/linear_scan.cpp) to see the complete code implementing the Linear Scan Index class and other utility methods. Below is just the logic for the Search methods of the Linear Index Class.

```cpp
// search in linear scan index
vector<pair<uint32_t , float>> LinearScanIndex::search(const Vector& query , size_t k) const {
    assert (query.dim == dim_);

    vector<pair<uint32_t, float>> results;

    results.reserve(data_.size());

    for(size_t_t i = 0; i<data_.size() ; ++i){
        dist_t d = l2_distance(query , data_[i]);
        results.emplace_back(i, d);
    }

    if(results.size() > k){
        nth_element(results.begin() , 
                    results.begin() + k,
                    results.end() , 
                    [](auto& a , auto& b) {return a.second < b.second ;}
                );
        results.resize(k);
    }

    sort(results.begin() , results.end() , 
        [](auto& a , auto& b) {return a.second < b.second ;}
    );

    return results;
}
```

# Let’s try & Optimize this Linear Scan

At this point the algorithm is still exactly the same. We are still comparing the query against **every** vector. We are still computing the exact L2 distance.

The only thing that changes now is **how efficiently the CPU is allowed to do the work**.

## Doing more work, per CPU cycle with AVX2

A modern CPU is not meant to process one floating-point number at a time. It has wide vector registers that can hold multiple values and operate on all of them in a single instruction. AVX2 gives us 256-bit registers, which means **8 floats at once**.

The idea behind AVX2 distance computation is simple:  
instead of computing : (a\_i - b\_i)²

one dimension at a time, we compute **eight of them together**.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1767604831476/7bd2ce1f-398a-4117-89df-496de15fa381.gif align="center")

If you look at the `l2_avx2` routine, the core loop moves through the vectors in chunks of 8. `_mm256_loadu_ps` loads 8 floats from memory into a single register. One register holds part of vector `a`, another holds the corresponding part of vector `b`.

Once both are in registers, subtraction happens in parallel for all 8 values. Squaring is also done in parallel, and the results are accumulated into a running sum. This accumulation uses a fused multiply-add instruction, which computes : sum = diff² + sum

in one step. This is both faster and numerically stable. What is important here is that the **inner loop becomes branch-free and dense**. The CPU sees a tight stream of predictable instructions, which is exactly what it likes.

```cpp
float l2_avx2(const float* a, const float* b, size_t dim) {
    __m256 sum = _mm256_setzero_ps();
    size_t i = 0;

    for (; i + 8 <= dim; i += 8) {
        __m256 va = _mm256_loadu_ps(a + i);
        __m256 vb = _mm256_loadu_ps(b + i);
        __m256 diff = _mm256_sub_ps(va, vb);
        sum = _mm256_fmadd_ps(diff, diff, sum);
    }

    float tmp[8];
    _mm256_storeu_ps(tmp, sum);

    float res = tmp[0] + tmp[1] + tmp[2] + tmp[3]
              + tmp[4] + tmp[5] + tmp[6] + tmp[7];

    for (; i < dim; ++i) {
        float d = a[i] - b[i];
        res += d * d;
    }

    return res;
}
```

Important Thing to Note : AVX does not do automatically is reduce a vector register to a single scalar. After the loop finishes, the sum still lives in a register holding 8 partial values.

To finish the distance computation, the register is stored back to memory and the 8 values are added together in normal scalar code. This step looks a bit ugly, but its cost is negligible compared to the main loop, especially for high-dimensional vectors.

Any leftover dimensions that do not fit into a multiple of 8 are handled at the end using a simple scalar loop. This ensures correctness for all dimensions without complicating the main vectorized loop. AVX2 does not change the number of arithmetic operations mathematically. It changes **how many are executed per CPU cycle**.

Instead of issuing one subtract and one multiply per dimension, the CPU now issues eight of them at once. Memory access also becomes more efficient because data is consumed in wide, predictable chunks.

> Below table is for the following setting : Dataset size : 100000 , Dimension : 1024 , Queries : 100 ,Top-K : 10

| **Implementation Type** | **Search Time** | **Queries Per Second (QPS)** | **instructions per cycle** |
| --- | --- | --- | --- |
| **Scalar** | 7.792 sec | 12.83 | 0.97 |
| **AVX2** | 2.339 sec | 42.74 | 1.04 |

## Multi-threading with OpenMP

Once distance computation is fast, the next bottleneck becomes obvious: there are still many vectors to process.

Each query–vector distance is independent of every other one. So our mind very quickly asks the question can we use Multi-Threading . The easiest form of parallelism is using OpenMP at the outer level which allows the loop over database vectors to be split across CPU cores with almost no code changes.

The key lesson here is that multi-threading only helps **after** the inner loop is efficient. Parallelizing slow code just gives you slow code running on multiple cores.

```cpp
#include <omp.h>

vector<pair<idx_t , dist_t>> LinearScanIndex::search(const Vector& query , size_t k) const {
    assert (query.dim == dim_);

    vector<pair<idx_t, dist_t>> results(aos_.size());
    
    auto compute = [&] (idx_t i) {
        dist_t d = l2_dispatch(query , aos_[i] , cfg_.distance);
        results[i] = {i , d};
    };

    if(cfg_.exec == ExecPolicy::OPENMP){
        #pragma omp parralel for schedule(static)
        for(idx_t i = 0 ; i<aos_.size() ; i++)compute(i);
    }else{
        for(idx_t i = 0 ; i<aos_.size() ; i++) compute(i);
    }

    if(results.size() > k){
        nth_element(results.begin() , 
                    results.begin() + k,
                    results.end() , 
                    [](auto& a , auto& b) {return a.second < b.second ;}
                );
        results.resize(k);
    }

    sort(results.begin() , results.end() , 
        [](auto& a , auto& b) {return a.second < b.second ;}
    );

    return results;
}
```

> Below table is for the following setting : Dataset size : 100000 , Dimension : 1024 , Queries : 100 ,Top-K : 10 , threads : 12

| **Implementation Type** | **Search Time** | **Queries Per Second (QPS)** | **instructions per cycle** |
| --- | --- | --- | --- |
| **Scalar** | 7.06 sec | 14.52 | 0.97 |
| **AVX2** | 2.025 sec | 44.07 | 1.05 |

## Memory layout: AoS vs SoA

Another optimization that matters more than expected is how vectors are stored in memory. With an array-of-structures layout, each vector is stored contiguously, but different vectors are interleaved. With a structure-of-arrays layout, each dimension is stored contiguously across all vectors.

For linear scan with AVX2, contiguous memory access is critical. When data is laid out in a cache-friendly way, the CPU can prefetch aggressively and avoid stalling on memory. A bad layout can completely erase the gains from SIMD and multithreading.

This is where theory meets reality: the same algorithm, the same math, but very different performance depending on layout.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1767430737818/d9ea5983-b864-483e-8a1a-d12d182a454c.gif align="center")

# KD Tree

After squeezing everything we could out of linear scan, the next logical step is to reduce the amount of work altogether. Instead of comparing the query against every vector, the goal now is to **avoid computing distances that clearly cannot matter**.

This is where KD-Trees come in. A KD-Tree recursively partitions the vector space by splitting along one dimension at a time. At each node, vectors are divided based on whether they lie on one side of a splitting value or the other. Over time, this creates a tree where nearby points in space tend to live close together in the structure.

The key idea is that if a region of space is far from the query, we can skip all vectors inside it without ever computing their distances.

## Building The Tree

The KD-Tree is constructed top-down. At the root, all vectors are considered. A splitting axis is chosen based on the current depth, usually by cycling through dimensions. Along that axis, vectors are sorted and split at the median. This guarantees that the tree remains roughly balanced.

Each node stores the splitting axis, the split value, and pointers to its left and right children. Leaf nodes contain a small set of vectors and act as stopping points for recursion.

This construction cost is paid once, offline. The real question is whether it pays off during search.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1767604199763/47d08f8c-6ec6-4a11-a0b6-68a864ed8c87.gif align="center")

## Querying the Tree

Searching the KD-Tree starts by descending into the subtree that contains the query point. This is the “greedy” path, following the side of the split where the query lies.

Once a leaf is reached, distances to its vectors are computed and the current best neighbors are updated. Then comes the crucial part: **backtracking**.

When backtracking, the algorithm checks whether the other side of a split could possibly contain a closer neighbor than the current best. This decision is made using geometry. If the distance from the query to the splitting plane is larger than the worst distance in the current top-k set, the entire subtree can be safely pruned.

This pruning is what makes KD-Trees fast in low dimensions. Large parts of the dataset are never touched.

## The curse of Dimensionality Shows up

As dimensionality increases, something interesting — and slightly depressing — happens.

Distances become less informative. Points start to look equally far from the query in all directions. The distance to the splitting plane rarely exceeds the current best distance, which means pruning almost never triggers.

In high dimensions, the KD-Tree ends up visiting most of the nodes. At that point, the search degenerates back into something very close to linear scan, with extra overhead from recursion and tree traversal.

> Below table is for the following setting : Dataset size : 100000 , Dimension , Queries : 1 ,Top-K : 10

| **dimension** | **linear Search Time** | **kd\_tree Search Time** | **Visited Nodes** | **Pruned Branches** |
| --- | --- | --- | --- | --- |
| **4** | 2.15 ms | 0.088 ms | 376 | 129 |
| **8** | 2.74 ms | 1.32 ms | 8982 | 3432 |
| **32** | 5.59 ms | 35.75 ms | 100000 | 0 |
| **128** | 17.11 ms | 64.73 ms | 100000 | 0 |
| **1024** | 158.299 ms | 188.459 ms | 100000 | 0 |

This is not a bug. It is a fundamental limitation . Implementing KD-Trees makes this painfully clear in practice, not just in theory.