# Vector Indexing

Course: [Retrieval-Augmented Generation](https://www.devtutorials.ai/learn/rag) · Section: Vector Search
Source: https://www.devtutorials.ai/learn/rag/vector-search/vector-indexing

> Storing and searching vectors at scale: vector database basics, persistence, flat vs approximate search, recall, IVF and HNSW indexes and their settings, and how to choose an index.

Finding a book in a small bookshop is easy: walk along the shelves and look at every spine. In a national library with millions of books, that would take days. Libraries solve it with organisation: books are grouped into sections by subject, and a catalogue points you to the right shelf. You might miss a book shelved in the wrong section, but you find almost everything in seconds.

A **vector index** is that organisation for vectors. It lets you find the nearest neighbours among millions of vectors without checking every one.

**The main idea:** a **vector database** stores vectors with their ids and metadata, keeps them on disk so they **persist**, and builds an **index** for fast search. **Flat** search checks every vector: it is exact, but slow at scale. **Approximate** indexes like **HNSW** (a graph of neighbours) and **IVF** (vectors grouped into lists around centres) check only a small part, trading a little **recall** for a lot of **speed**.

## A Real-World Example

Brightgrid's help center had 2,000 chunks, and flat search in the browser took under a millisecond. Then the company decided to also index 20 million chunks from five years of support tickets, on a server.

Flat search over 20 million vectors of 384 numbers takes billions of calculations per question. Each search took several seconds, far too slow for a chat.

They moved the tickets into a vector database with an **HNSW** index. Searches dropped to a few milliseconds. They measured **recall@10**, the share of the true top 10 that the index found, at about 0.97. For the small help center, they kept flat search, because it is exact and already fast.

**In simple words:** small collection, check everything. Huge collection, use a smart index and measure what it misses.

## What You Will Learn

In this lesson, you will learn:

1. Vector database fundamentals: what they store and what they do.
2. Persistence: saving and loading vectors.
3. Index structures: flat vs approximate nearest neighbour (ANN) search.
4. How HNSW and IVF work, and how to tune them.

The RAG Lab keeps its few dozen chunk vectors in memory and uses flat search, which is exact and instant at this size. The cells below build small versions of persistence, IVF and HNSW so you can see how the large-scale structures work.

## Vector Storage

### Vector Database Fundamentals

A **vector database** stores, for each chunk:

- An **id**, like `returns-policy#1`.
- The **vector**, like 384 numbers.
- A **payload** of metadata: text, title, dates, region, access tags.

On top of that it offers:

- **Search:** "the k nearest vectors to this one", usually **with metadata filters**.
- **Updates:** add, change and delete records without rebuilding everything.
- **Index structures** for speed, persistence, backups and scaling across machines.

Popular options include dedicated vector databases and vector extensions for databases you may already use, such as PostgreSQL with pgvector. For small collections, a simple array in memory, like the RAG Lab's, is a perfectly good "database".

### Vector Persistence

Embedding is slow and costs money, so vectors should be **saved**, not recomputed on every restart. Vectors are just numbers, so the most compact way to store them is as raw **float32 bytes**: 4 bytes per number. Store the **shape** (how many vectors, how many dimensions) and the **model name** alongside them.

```js runnable title="Save vectors as bytes and load them back"
// Persistence: save vectors as raw bytes, then load them back exactly.
const vectors = [
  [0.12, -0.53, 0.88],
  [0.31, 0.27, -0.91],
];
const dims = 3;

// Save: one Float32Array holding all numbers, plus a small header with the shape.
const flat = new Float32Array(vectors.length * dims);
vectors.forEach((v, i) => flat.set(v, i * dims));
const saved = { count: vectors.length, dims, bytes: new Uint8Array(flat.buffer) };
console.log(
  `saved ${saved.count} vectors x ${saved.dims} dims = ${saved.bytes.length} bytes`,
);

// Load: view the same bytes as numbers again.
const loaded = new Float32Array(saved.bytes.buffer);
for (let i = 0; i < saved.count; i++) {
  const v = Array.from(loaded.slice(i * dims, (i + 1) * dims));
  console.log(`vector ${i}:`, v.map((x) => x.toFixed(2)).join(", "));
}
console.log("float32 keeps about 7 significant digits:", loaded[0]);
```

Expected output:

```text
saved 2 vectors x 3 dims = 24 bytes
vector 0: 0.12, -0.53, 0.88
vector 1: 0.31, 0.27, -0.91
float32 keeps about 7 significant digits: 0.11999999731779099
```

In the browser, IndexedDB can hold these bytes between visits. On a server, the vector database handles it for you.

## Vector Index Structures

### Flat Search and Its Limits

**Flat** search compares the query with every vector. It is exact and simple, but its cost grows with the number of vectors:

```js runnable title="How flat search scales"
// Flat (brute-force) search compares the query with every vector. Count the work.
const dims = 384;
console.log("vectors      multiply-adds per query   at 1 billion per second");
for (const n of [1000, 100000, 10000000, 1000000000]) {
  const ops = n * dims;
  const ms = (ops / 1e9) * 1000;
  console.log(
    `${n.toLocaleString("en-US").padStart(13)}  ${ops.toExponential(1).padStart(22)}   ${ms < 1 ? ms.toFixed(2) : Math.round(ms).toLocaleString("en-US")} ms`,
  );
}
```

Expected output:

```text
vectors      multiply-adds per query   at 1 billion per second
        1,000                  3.8e+5   0.38 ms
      100,000                  3.8e+7   38 ms
   10,000,000                  3.8e+9   3,840 ms
1,000,000,000                 3.8e+11   384,000 ms
```

Up to about 100,000 vectors, flat search is usually fine, especially with fast hardware. Beyond that, you need an **ANN** index. **ANN** means **approximate nearest neighbour**: it finds almost all of the true nearest vectors, much faster.

### Recall: Measuring What ANN Misses

**Recall@k** is the share of the true top k (from flat search) that the index also returns. A recall@10 of 0.95 means that, on average, the index finds 9.5 of the real 10 nearest chunks. Measure recall on your own data, because it depends on your vectors and settings.

### IVF Indexing

**IVF** (inverted file index) works like library sections:

1. **Build:** find a few hundred or thousand **centres** with k-means, and put each vector in the **list** of its nearest centre.
2. **Search:** find the centres nearest to the query, and compare the query only with the vectors in those lists.

The key setting is **nprobe**: how many lists to search. Higher nprobe means better recall but more comparisons. A query near the border between two groups needs nprobe of at least 2, because its neighbours live in both lists:

```js runnable title="IVF with different nprobe values"
// IVF (inverted file index): group vectors into lists around centres, then search only
// the lists closest to the query. Fewer comparisons, small risk of missing a match.
let seed = 7;
const rand = () => (seed = (seed * 16807) % 2147483647) / 2147483647;
const pts = Array.from({ length: 400 }, (_v, i) => {
  const c = i % 4; // four natural groups
  return { id: i, v: [Math.floor(c / 2) * 4 + rand(), (c % 2) * 4 + rand()] };
});
const dist = (a, b) => Math.hypot(a[0] - b[0], a[1] - b[1]);

// Build: pick 4 centres and put every point in the list of its nearest centre.
const centres = [pts[0].v, pts[1].v, pts[2].v, pts[3].v];
const lists = centres.map(() => []);
for (const p of pts) {
  const near = centres.map((c) => dist(p.v, c));
  lists[near.indexOf(Math.min(...near))].push(p);
}

const query = [2.5, 0.5]; // halfway between two groups
const exact = [...pts]
  .sort((a, b) => dist(a.v, query) - dist(b.v, query))
  .slice(0, 5)
  .map((p) => p.id);

for (const nprobe of [1, 2, 4]) {
  const order = centres
    .map((c, i) => ({ i, d: dist(c, query) }))
    .sort((a, b) => a.d - b.d);
  const candidates = order.slice(0, nprobe).flatMap((o) => lists[o.i]);
  const found = candidates
    .sort((a, b) => dist(a.v, query) - dist(b.v, query))
    .slice(0, 5)
    .map((p) => p.id);
  const recall = found.filter((id) => exact.includes(id)).length / exact.length;
  console.log(
    `nprobe ${nprobe}: compared ${String(candidates.length).padStart(3)} of ${pts.length}, recall@5 = ${recall.toFixed(2)}`,
  );
}
```

Expected output:

```text
nprobe 1: compared 100 of 400, recall@5 = 0.20
nprobe 2: compared 200 of 400, recall@5 = 1.00
nprobe 4: compared 400 of 400, recall@5 = 1.00
```

IVF is memory-friendly and pairs well with **quantization**, which compresses the vectors in each list.

### HNSW Indexing

**HNSW** (Hierarchical Navigable Small World) links each vector to a handful of **neighbours**, making a graph. To search, start at an entry point and repeatedly jump to the neighbour that is closest to the query, until no neighbour is closer. The "hierarchical" part adds sparse upper layers with long links, like motorways, so the walk crosses the space quickly, then switches to the detailed lower layers, like local streets, to finish.

```js runnable title="A greedy walk through a small graph"
// HNSW in miniature: a graph where each vector links to near neighbours.
// Search walks from an entry point, always moving to the neighbour closest to the query.
const pos = {
  A: [0, 0],
  B: [2, 1],
  C: [4, 0],
  D: [5, 3],
  E: [7, 2],
  F: [8, 5],
  G: [3, 4],
};
const links = {
  A: ["B", "G"],
  B: ["A", "C", "G"],
  C: ["B", "D", "E"],
  D: ["C", "E", "F", "G"],
  E: ["C", "D", "F"],
  F: ["D", "E"],
  G: ["A", "B", "D"],
};
const dist = (a, b) => Math.hypot(pos[a][0] - b[0], pos[a][1] - b[1]);

function greedySearch(entry, q) {
  let cur = entry;
  const path = [cur];
  let checks = 0;
  for (;;) {
    let best = cur;
    for (const n of links[cur]) {
      checks += 1;
      if (dist(n, q) < dist(best, q)) {
        best = n;
      }
    }
    if (best === cur) {
      return { found: cur, path, checks };
    }
    cur = best;
    path.push(cur);
  }
}

const r = greedySearch("A", [7.5, 4.5]);
console.log(`path ${r.path.join(" -> ")}, nearest = ${r.found}`);
console.log(`hops: ${r.path.length - 1}, distance checks: ${r.checks}`);
console.log(
  "On 7 points this saves nothing. On millions, the walk still needs only a few hundred checks.",
);
```

Expected output:

```text
path A -> G -> D -> F, nearest = F
hops: 3, distance checks: 11
On 7 points this saves nothing. On millions, the walk still needs only a few hundred checks.
```

Its main settings:

- **M:** how many neighbours each vector links to. More links give better recall and use more memory.
- **efConstruction:** how carefully the graph is built. Higher means a better graph and a slower build.
- **efSearch:** how many candidates are kept during a search. Higher means better recall and slower search.

HNSW is fast and accurate, and the most common default in vector databases. Its costs are memory for the links, and slower handling of deletes and very frequent updates.

### Choosing an Index

| Index | Speed | Recall | Memory | Good for |
| --- | --- | --- | --- | --- |
| **Flat** | Slow at scale | Exact (1.0) | Lowest | Up to about 100k vectors, or when exactness is required |
| **IVF** | Fast | High, tune nprobe | Low, especially with quantization | Very large collections, tight memory |
| **HNSW** | Very fast | Very high, tune efSearch | Higher (graph links) | Large collections that need low latency |

```js runnable title="Pick an index for each situation"
// Choosing an index: flat for small or exact needs, HNSW or IVF for large collections.
function chooseIndex({ vectors, needExact, memoryTight }) {
  if (needExact || vectors < 50000) {
    return "flat (exact, simple, fast enough at this size)";
  }
  if (memoryTight) {
    return "IVF with quantized vectors (smaller memory, tune nprobe for recall)";
  }
  return "HNSW (fast and high recall, uses more memory for the graph)";
}

for (const c of [
  { name: "help center, 2,000 chunks", vectors: 2000 },
  { name: "legal archive, must be exact", vectors: 900000, needExact: true },
  { name: "all tickets, 20 million chunks", vectors: 20000000 },
  { name: "phone app, 5 million chunks", vectors: 5000000, memoryTight: true },
]) {
  console.log(`${c.name.padEnd(32)} -> ${chooseIndex(c)}`);
}
```

Expected output:

```text
help center, 2,000 chunks        -> flat (exact, simple, fast enough at this size)
legal archive, must be exact     -> flat (exact, simple, fast enough at this size)
all tickets, 20 million chunks   -> HNSW (fast and high recall, uses more memory for the graph)
phone app, 5 million chunks      -> IVF with quantized vectors (smaller memory, tune nprobe for recall)
```

Filters and ANN interact. If a filter removes most vectors, like "region = EU" when only 2% are EU, an ANN search may return too few results. Good vector databases filter **during** the search. Otherwise, store filtered groups in separate indexes or collections.

Never assume an ANN index is "basically exact". Measure **recall@k** against flat search on a sample of real questions, both when you first tune it and after big data changes.

## Common mistakes

- **Using an ANN index for tiny data**, which adds complexity and loses exactness for no gain.
- **Never measuring recall**, so missed results go unnoticed.
- **Losing vectors on restart** because they were never persisted.
- **Mixing vectors from two models** in one index after a model upgrade.
- **Heavy filters with ANN** that return far fewer than k results.

## Exercises

Each exercise ends with a value on the last line. Press **Check** to compare it with the expected answer.

## What to Remember

- A **vector database** stores ids, vectors and metadata, and offers filtered nearest-neighbour search, updates and persistence.
- **Persist** vectors as float32 bytes, with their shape and model name.
- **Flat** search is exact and fine up to about 100k vectors. Beyond that, use an **ANN** index.
- **IVF** searches only the lists around the nearest centres; tune **nprobe**. **HNSW** walks a graph of neighbours; tune **M** and **efSearch**.
- Always measure **recall@k** against flat search, and watch how **filters** interact with ANN.

Next: **Chapter 4, Top-K Retrieval**, score thresholds, the search flow and quality control.