Vector Search: Brute Force KNN and the Indexing Problem

The movie search from note 8 is quick. Type "a lost astronaut trying to get home", wait a moment, and The Martian comes back first. It feels done. Now picture the same code at a music app with 80 million songs, or a shop with 300 million products. The same loop that took a blink for 30 films now has to run hundreds of millions of times for every single search. This note is about what breaks, and why the usual database tricks do not fix it.

Note 8 built Reelbox, a search box that ranks 30 films by meaning. Here we take that idea apart. We build the simplest possible vector database by hand, count exactly how much work and memory it needs, and then try to speed it up with an index, the way a normal database would. A k-d tree works well in 2 dimensions. Then it stops helping as the dimensions grow. The code is a small lab in plain Java, Node.js and Python under code/09-brute-force-vector-search/. No API key is needed.

Here are the words used in this note. Each one is explained again the first time it shows up, but this table is the short version:

1. Where Note 8 Left Us

Reelbox has 30 films. Each one has a title, a short description and an embedding of that description. All of it sits in a plain list in memory.

record Movie(String title, String description, float[] embedding) { }

List<Movie> movies; // 30 of them, each embedding has 1,536 numbers

When someone searches, the app does four things.

Only the first box calls a model. Everything after it is a loop over a list and some arithmetic.

With toy vectors of three named numbers, [space, crime, love], the scores for that query look like this:

The three space films come out on top. For 30 films this approach is completely fine. There is nothing to fix yet.

2. Now Make It Big

Change only one thing: the number of items.

Every arrow multiplies the size. The search loop does not change at all. It just has more to walk through.

A few more places where the list gets long fast:

• A food delivery app that embeds every dish on every menu in a country. Tens of thousands of restaurants, dozens of dishes each.
• A support team that embeds every past ticket so agents can find "tickets like this one". Ten years of tickets is millions of rows.
• A photo app that embeds every photo a user has uploaded. One heavy user alone can have 50,000.

At that size, List<Movie> stops looking like a good home.

3. Two Problems, Not One

Growing the list creates two separate questions.

They are linked, but solving one does not solve the other.

Think of a large parcel warehouse. Having enough shelves for a million parcels is one problem. Finding the ten parcels whose delivery address is closest to a given street, in under a second, is a different problem. More shelves do not help with the second one at all.

4. Can a Normal Database Hold Vectors?

A common first thought: we already have MySQL or Postgres. Why not put the vectors there?

You can. A table like this is perfectly legal:

CREATE TABLE movies (
    id          INT PRIMARY KEY,
    title       VARCHAR(200),
    description TEXT,
    embedding   JSON          -- works, but bulky; a blob or a vector type is more compact
);

The same vector can land in that column in three ways:

A vector is just a list of numbers. Any database can store a list of numbers in some form. JSON text is the bulkiest and slowest to read back, because every number is written as characters.

So the sentence "normal databases cannot store vectors" is wrong. Storage is not the hard part. The hard part is the question we want to ask of those vectors.

A normal database can store vectors. The hard part is searching them by similarity.

5. The Questions Databases Are Built For

Look at the kind of query a database answers every day:

SELECT * FROM tickets WHERE pnr = '4521873690';
SELECT * FROM matches WHERE runs_scored > 300;
SELECT * FROM orders  WHERE placed_at BETWEEN '2024-01-01' AND '2024-01-31';

Each one is a yes or no test on every row. Is this PNR exactly 4521873690? Is this score above 300? Is this date inside January?

The building blocks are =, >, <, BETWEEN, LIKE, JOIN and GROUP BY. Under all of them sits one question: which rows satisfy my condition?

6. Vector Search Asks a Different Question

Say the query vector is Q = [0.3, 0.7, 0.2], and three stored vectors are:

A = [0.31, 0.69, 0.22]
B = [0.28, 0.72, 0.19]
C = [-0.6, 0.1, 0.8]

None of them is equal to Q. An exact match test would return nothing. But A and B are clearly almost the same as Q, and C is not.

In semantic search an exact match is almost useless. People word the same idea in many ways, so a query vector is almost never equal to a stored one. What we want instead is: which stored vectors are closest to Q?

The left question gets an empty answer. The right question gets the useful one.

That second question has a name: nearest neighbour search. Asking for the 10 closest is a K nearest neighbour search, or KNN, with K = 10.

7. Exact Lookup vs Similarity Lookup

Here are both kinds side by side.

An exact lookup gives a switch: on or off. A similarity lookup gives a dial: every stored item gets a score, and we keep the highest.

A phone contact list is a good picture of the difference. "Call Priya Sharma" is an exact lookup. You find the name or you do not. "Find people who live near me" is a similarity lookup. Nobody lives at exactly your address, so the only sensible answer is a short list, nearest first.

The left side ends after one match. The right side always has an answer, and the answer is a ranking.

Same thing on a film app. A user who loved Gravity does not want to search for "Gravity" and get Gravity back. They want films like Gravity. That is a similarity problem, not an exact match problem.

8. The Simplest Vector Database

Forget Pinecone, Qdrant, Weaviate, Milvus and pgvector for a moment. If we had to build a vector search system ourselves with nothing but a list and a loop, what would it need?

Three steps.

That is the whole design. The next three sections take one step each.

9. Step 1: Store the Vectors

At the very least we need a table with two columns:

id    vector
M1    [0.21, 0.72, 0.13, ...]
M2    [0.81, 0.11, 0.45, ...]
M3    [0.18, 0.69, 0.15, ...]

In practice we keep a third thing next to each vector: metadata. That is plain facts about the item, like title, genre and year.

The search only looks at the vector. The id and metadata are what we show the user once a vector wins.

Why each part is needed:

That last row matters. Similarity search and normal filters work together in real apps. A shop wants "jackets like this one, in my size, in stock". A food app wants "dishes like butter chicken, from places open now". Note 10 comes back to filtering.

10. Step 2: Turn the Query into a Vector

The user types words. The store holds numbers. We cannot compare words with numbers, so the query goes through the same embedding model that made the stored vectors.

The model is called once per search. The vector store never sees the words.

It must be the same model. Each model turns text into numbers in its own way, so vectors from two models cannot be compared. A price in rupees and a price in yen are both numbers too, but you cannot compare them directly.

This also shows a clean split of jobs:

The vector store does not know that Interstellar is about space, survival and astronauts. The embedding model put that knowledge into the numbers. The store only finds numbers that are close to other numbers.

The embedding model creates the meaning. The vector store only searches it.

11. Step 3: Compare with Every Vector

The simplest search computes a score for every stored vector. The score says how alike two vectors are (cosine similarity, from note 7):

similarity(Q, M1)
similarity(Q, M2)
similarity(Q, M3)
...
similarity(Q, M30)

Then it sorts and keeps the top K.

Every stored vector gets an arrow from the query. Nothing is skipped.

With the seven toy films from section 1 and K = 3, the answer is The Martian (0.985), Gravity (0.976) and Interstellar (0.972). That is a working K nearest neighbour search. It took one loop.

12. What K Means

Picture the query as a point on a map, with stored vectors as other points around it.

The numbers on the lines are distances. Shorter means more similar.

• K = 1 returns A.
• K = 3 returns A, B and D.
• K = 5 returns all five, nearest first.

K is simply how many neighbours you want. A map app showing "the 3 nearest ATMs" is running a KNN with K = 3. A film app's "more like this" row with 10 posters is K = 10.

13. The Code: Brute Force Top K

Here is the search from the lab in Python, without the input checks:

def search_exact(self, query, k):
    query_length = vector_length(query)
    heap = []          # min heap: heap[0] is the weakest of the best K so far
    comparisons = 0
    for position, entry in enumerate(self._entries):
        score = dot(query, entry.vector) / (query_length * entry.length)
        comparisons += 1
        if len(heap) < k:
            heapq.heappush(heap, (score, position, entry))
        elif score > heap[0][0]:
            heapq.heapreplace(heap, (score, position, entry))  # kick out the weakest

    best = sorted(heap, key=lambda item: item[0], reverse=True)
    matches = [Match(entry.id, score, entry.metadata) for score, _, entry in best]
    return SearchResult(matches, comparisons, comparisons * self._dimensions)

Two small choices are worth pointing at. The length of each stored vector is worked out once, when it is added, not on every search. And instead of sorting all N scores, it keeps a heap of size K. Section 20 explains the heap. The position in each heap item only breaks ties between equal scores, so Python never has to compare two entries. The last line reports multiply-adds as comparisons times dimensions.

14. Brute Force Is Correct

Brute force has one big strength. It checks every vector. So if the true three nearest vectors are A, B and C, it will find A, B and C. Always.

The result is right every time. The cost goes up with every item added.

This is called exact nearest neighbour search. The word "exact" matters, because note 10 gives it up on purpose.

The trade looks like this:

Keep this picture in mind. Every speed trick in note 10 moves away from "check everything" and pays for it with a little accuracy.

15. Why It Gets Slow: N Comparisons per Query

With 100 stored vectors, one search does 100 comparisons. Nobody notices.

With 100,000,000 stored vectors, one search does 100,000,000 comparisons. And that is one user pressing enter once.

The work grows in a straight line with the number of vectors. Double the catalogue, double the work. No step ever gets cheaper.

A busy app does not get one search at a time. It may get thousands every second. Each of them repeats the full scan.

Think of a teacher who has to find the five students whose handwriting looks most like a note found in class. With one class of 40, she can check every copy book. With every school in the city, the same method is still correct. It just never finishes.

16. One Comparison Is D Multiply-Adds

There is a second multiplier hiding inside each comparison.

A comparison is not one step. For cosine similarity we multiply the two vectors position by position and add the results. With the toy vectors:

query       = [0.9,  0.2,  0.1 ]
The Martian = [0.95, 0.05, 0.05]

0.9 x 0.95 = 0.855
0.2 x 0.05 = 0.010
0.1 x 0.05 = 0.005
                ------
sum         = 0.870     (3 multiply-adds)

Three dimensions, three multiply-adds. A real embedding from text-embedding-3-small has 1,536 dimensions, so one comparison is about 1,536 multiply-adds.

That is why people write the cost of brute force as O(N x D). Read it as "the work grows with the number of vectors times the number of dimensions".

Suppose every stored vector is scaled to length 1 ahead of time. Then cosine is just the multiply-and-add sum above, called the dot product (note 7). That saves a division per comparison. All D multiply-adds still happen.

17. Putting Real Numbers on It

Take 10,000,000 vectors of 1,536 dimensions:

10,000,000 x 1,536 = 15,360,000,000 multiply-adds

That is about 15.36 billion for a single query.

Here is the same sum at four sizes. These are the numbers the lab prints:

Now a made up round number, just to feel the size. Say one server could do 10 billion multiply-adds every second. Then:

The exact speed of a real machine differs a lot. Special CPU instructions and GPUs can do many multiply-adds at once. But the shape stays the same: the work grows with the size of the data.

With brute force, every new vector makes every future search a little slower.

18. The Memory Bill

The second problem is memory.

One float32 number takes 4 bytes. One vector of 1,536 of them takes:

1,536 x 4 bytes = 6,144 bytes, about 6 KB

Multiply by the catalogue. This counts raw float32 bytes. The same vector stored as JSON text takes more space, because every number is written out as characters.

const dimensions = 1536;
const bytesPerNumber = 4;                              // float32
const bytesPerVector = dimensions * bytesPerNumber;     // 6,144

for (const vectors of [1_000_000, 100_000_000]) {
  const total = vectors * bytesPerVector;
  console.log(vectors, formatBytes(total));             // 6.14 GB, then 614.40 GB
}

Follow one vector as the count grows:

The last box is easy to forget. The raw numbers are only the floor.

The lab prints sizes in steps of 1,000 (KB, MB, GB), the way disk makers and cloud bills count. Your laptop may count in steps of 1,024 and show the same 6,144,000,000 bytes as 5.72 GiB. Same bytes, different ruler.

On top of the raw vectors, a real system also stores:

• the ids and the metadata for each item
• the index structures that make search faster (note 10)
• copies on other machines, so one broken disk does not lose everything
• working memory for searches that are running right now

So vector search has two bills at once: a compute bill and a memory bill.

19. Why Not Keep Everything on Disk?

Memory is expensive. Disks are cheap. Why not leave the vectors on disk?

That fixes the space problem and makes the speed problem worse. A brute force search has to read every vector for every query.

Even a fast SSD that reads a few GB every second needs seconds just to read 6 GB once. And the next query reads it all again.

A kitchen is a good picture. Memory is the counter right next to the stove. The disk is the storeroom at the back. A cook can keep a hundred times more in the storeroom, but if every pinch of salt needs a walk to the back, dinner is late. Moving the vectors to disk does not solve search. It only moves the problem.

20. Finding the Top K Has a Cost Too

After scoring, we have a long list:

M1 -> 0.71
M2 -> 0.23
M3 -> 0.94
M4 -> 0.51
...

We need the K highest. The obvious way is to sort the whole list and take the first K. With a million scores that sorts a million items to keep 10.

A heap does better. Think of a sports trial that only keeps the three fastest times on a small board. A new runner finishes. If their time is better than the worst time on the board, the worst one is wiped off and the new one goes up. Otherwise nothing changes. The board never holds more than three times, and you only ever compare with its weakest entry.

A min heap is built for exactly this. Its smallest item is always on top, so "is this better than the weakest?" is one look.

Here log means "how many times you can halve the number". With N = 1,000,000 and K = 10, log N is about 20 and log K is about 3. The heap is several times less work, and it only ever holds 10 items.

Java has PriorityQueue and Python has heapq. JavaScript has no heap built in, so the Node version of the lab has a small TopKHeap class.

21. The Three Costs of Brute Force

Put together, one brute force search pays three costs.

1. Read or fetch every vector, from memory or, worse, from disk.
2. Compare the query with every vector, N times D multiply-adds.
3. Select the best K, with a heap or a partial sort.

The heap makes step 3 cheap. Steps 1 and 2 are the real problem, and they both grow with N.

22. Can We Skip Vectors?

So here is where we stand:

• Brute force is always right.
• Brute force reads and scores everything, every time.

That raises the obvious question: can we avoid even looking at vectors that clearly cannot be good answers?

Ruling things out early, without looking at them, is exactly what an index does in a normal database. So let us see how a normal index works, and whether it carries over.

23. Why a Normal Index Works

Take a food delivery app with 10 million orders. We run:

SELECT * FROM orders WHERE bill_amount = 450;

With no index, the database has to read every row and test it:

120   no
800   no
450   match
260   no
450   match
...   (10 million rows)

That is a full scan, which is brute force by another name.

With an index on bill_amount, the values are kept in order:

120  180  260  310  450  450  520  800

Order is the secret. Say we are looking for 450 and we land on 310. We know at once that everything to the left of 310 is smaller. There is no point looking there. We only move right.

Each step throws away half of what is left. That is binary search. A million sorted values need only about 20 steps.

A paper dictionary works the same way. Looking for "mango", you open near the middle, see "kettle", and you never look at any page before it again.

An index is fast because order lets it throw away most of the data without reading it.

24. B-Trees in One Picture

Databases do not keep one long sorted list. They keep a B-tree: a short, wide tree of sorted values. Each node holds a few values and points to children for the ranges between them.

Searching for 450: it is between 300 and 600, so go to the middle child. It is between 400 and 500, so go to the middle again. The left and right parts of the tree are never touched.

Every step down rules out whole branches. That only works because numbers like 450 have one clear order: every value is either smaller, equal or bigger. Keep that in mind, because it is about to stop being true.

25. Nearest in One Dimension

A B-tree finds exact values. Can a tree also find the nearest value? In one dimension, yes.

Picture bus stops along one straight highway, marked by kilometre: 2, 5, 9, 14, 20, 27 and 33. You are standing at km 16. Which stop is nearest?

Put the stops in a tree, with the middle one on top:

The walk for km 16:

1. At 14. Distance 2. Best so far: 14. Since 16 is bigger, go right.
2. At 27. Distance 11. Since 16 is smaller, go left.
3. At 20. Distance 4. Still not better than 14.
4. Could anything on the left of 14 be closer? Every stop there is below 14, so it is at least 2 km from you (the gap from 16 to 14). We already have a stop 2 km away. Skip the whole left side.

We checked 3 of 7 stops. The answer is km 14. The left branch, with 2, 5 and 9, was never touched. Stop 33 was skipped too: it is past km 27, so at least 11 km away. On a line, order makes nearest search fast too.

26. Two Dimensions Break the Order

Now give each point two numbers, like a place on a city map: [x, y].

P = [3, 9]
R = [7, 2]

Which one is smaller? By x, P is smaller (3 is less than 7). By y, R is smaller (2 is less than 9). There is no single answer.

Two honest ways to sort, two different answers. A single sorted list can only follow one of them.

A cricket team has the same problem. Sort the players by batting average and you get one order. Sort them by wickets and you get another. Neither list tells you who is the best all rounder. Once there is more than one number per item, "smaller" and "bigger" stop being simple.

27. Split One Axis at a Time: the k-d Tree

One way out is to stop trying to sort everything at once. Split the space on one dimension, then split each half on the next dimension, and keep going round. This is a k-d tree, short for k-dimensional tree.

In two dimensions:

1. Draw a vertical line at some x. Everything left goes one way, everything right goes the other.
2. Inside each half, draw a horizontal line at some y.
3. Inside each quarter, go back to x. And so on.

Each level of the tree cuts the regions in half again, always along one axis at a time. In 3D the cycle is x, y, z, x, y, z.

A town planner does something similar when splitting a city into wards. First cut east from west along the main road. Then cut each side north from south along the railway. Each ward is a box, and you can tell which ward a house is in with two quick questions.

28. Building a Small k-d Tree by Hand

Here are seven tea stalls on a 10 by 10 city map. These are the exact points the lab uses.

The rule: at each level, sort the points on that level's axis, put the middle one in the node, and send the rest left and right.

Level 0 splits on x. Sorted by x the order is A, B, C, D, E, F, G. The middle is D, at x = 6. A, B and C go left. E, F and G go right.

Level 1 splits on y.

• Left side sorted by y: B (2), A (7), C (9). The middle is A. B goes left, C goes right.
• Right side sorted by y: E (1), G (4), F (8). The middle is G. E goes left, F goes right.

Left children have the smaller value on their parent's axis. B has y = 2, below A's 7. F has y = 8, above G's 4. A tie can land on either side when the tree is built. When searching, a query with a smaller value goes left, and a query exactly on the line goes right.

Picking the middle each time keeps both sides the same size. Seven points fit in 3 levels. A million points fit in about 20.

In code, a node is tiny. This is the Java shape from the lab:

/** A named point, for example a tea stall on a city map. */
public record Point(String id, double[] coords) { }

/**
 * One node: the point stored here, the axis it splits on, and both sides.
 * Points with a smaller value on that axis went left, the rest went right.
 */
public record Node(Point point, int axis, Node left, Node right) { }

axis is 0 for x and 1 for y. The build sets it to depth % dimensions, which is what makes the tree cycle through the axes.

29. Searching the Tree: a Query That Prunes Well

You are standing at Q = [9, 7] and want the nearest stall. The search goes down the side the query falls on, keeps the best stall seen so far, and on the way back checks whether the other side could possibly hold anything closer.

1. At D (6, 5). Distance from Q is about 3.61. Best so far: D. The split is x = 6 and Q's x is 9, so Q is on the right. Go right first.
2. At G (9, 4). Distance 3. Best so far: G. The split is y = 4 and Q's y is 7, so go right first.
3. At F (8, 8). Distance about 1.41. Best so far: F. F has no children.
4. Back at G. Could E's side be closer? To get there you cross the line y = 4, which is 3 away from Q. Our best is 1.41. No. Skip E.
5. Back at D. Could the left side be closer? You would cross the line x = 6, which is 3 away. Our best is 1.41. No. Skip A, B and C.

Three stalls visited out of seven. Four were ruled out without measuring them. That is pruning, and it is what makes an index worth having.

30. A Query That Cannot Prune

Now stand at Q = [6.5, 2.5]. This is just to the right of the first split line, x = 6.

1. At D (6, 5). Distance about 2.55. Best: D. Q's x is 6.5, so go right.
2. At G (9, 4). Distance about 2.92. Not better. Q's y is 2.5, below G's 4, so go left.
3. At E (7, 1). Distance about 1.58. Best: E.
4. Back at G. F's side is across y = 4, which is 1.5 away. Our best is 1.58. 1.5 is less than 1.58, so F might be closer. We must check F. It is about 5.70 away. Not better.
5. Back at D. The left side is across x = 6, which is only 0.5 away. We must check it. A is about 6.36 away. B is about 3.54 away. Neither is better.
6. C sits across A's line y = 7, which is 4.5 away. That is more than 1.58. Skip C.

Six of seven visited. Only C was skipped. The tree still found the right answer, but it saved almost no work, because the query sat close to a split line.

The lab's demo and tests run both of these searches and check the paths: D, G, F for the first and D, G, E, F, A, B for the second.

31. The Pruning Rule in One Line

Both walks used the same test at every node:

Every point on the far side lies beyond the split line, so it is at least gap away from the query. If even that is no better than our best so far, nothing over there can win.

Pruning works when the query is far from the split lines and a close answer has already been found. It fails when the query is near a line, or when the best distance so far is still large. Hold on to the second part.

In the lab's code the test compares squared numbers, gap * gap < bestSquared. This skips a square root, which is slow work. The decision is the same.

32. Three Dimensions and Beyond

In 2D a query may be close to the x line but far from the y lines, so some pruning still happens. k-d trees are really useful in low dimensions: map points, game objects in 3D, colours as [red, green, blue].

Add a third axis and there are more split lines around every query. More chances to be close to one. More branches that cannot be ruled out.

Each step to the right gives the query more boundaries to sit near and the tree fewer chances to say "definitely not over there".

33. The Curse of Dimensionality

There are two plain reasons a k-d tree fails on embeddings.

The first is that the tree is short for so many dimensions. A tree with 1,000,000 points is only about 20 levels deep, and each level splits on one axis. So a search only ever asks about 20 of the 1,536 dimensions. The other 1,516 never get a split line, but they still count towards every distance.

The second is that everything is far away. Every dimension adds a little to the distance between two points. With many dimensions, even the nearest point is far away in total. A split line is measured on one axis only, so it is always close by comparison.

Here is a concrete case. Points are random inside a box that is 1 unit wide on every side. The lab uses random points like this but prints only visit shares, so the distances below are rough figures from a quick check, not lab output.

• In 2D, with 20,000 points, the nearest point is usually a tiny fraction of a unit away. Most split lines are further than that, so whole branches get pruned.
• In 32D, with the same 20,000 points, the nearest point is usually more than 1 unit away. A split line can never be more than 1 unit away, because the whole box is 1 unit wide. So the test "is the line further than my best?" says no almost every time, and nothing gets pruned.

Both causes meet in the same place: the pruning test keeps saying "you have to look".

There is a strange side effect too. In very high dimensions, random points end up at almost the same distance from each other. The nearest and the farthest are not that different. Imagine a city where every shop is about 4 km from your house, give or take a few hundred metres. A map index cannot help you much, because no shop is clearly out of range.

This is what people mean by the curse of dimensionality. Tricks that split space into boxes work well in 2 or 3 dimensions and stop working as dimensions grow.

In high dimensions a k-d tree ends up visiting almost everything, which is brute force with extra steps.

34. What the Lab Measures

The last part of the demo makes this visible. For each of D = 2, 3, 8, 32 and 128, it:

1. makes 20,000 random points with D numbers each, from a fixed seed
2. builds a k-d tree over them
3. runs 20 random queries
4. prints the average number of nodes visited, as a share of 20,000, with a text bar

The exact numbers depend on the random data, so the lab's README describes them rather than quoting them. The shape is what matters: the bar climbs towards full as D grows. A full bar means the tree measured every point, which is what the plain loop in section 13 does with far less code.

Real embeddings are not spread evenly in a box. They clump together by topic, which can help a little. But at hundreds or thousands of dimensions a k-d tree still ends up close to brute force.

35. The Core Problem

The whole story so far, in one picture:

The last box is the question note 10 answers.

Normal indexes win by throwing away most of an ordered search space. Vectors have no single order. Splitting space into boxes helps in 2D and stops helping long before 1,536D. So exact search over millions of embeddings stays expensive.

The way out is to stop insisting on the exact answer. If a search can return results that are very close to the true nearest neighbours, while looking at only a small share of the vectors, most apps are happy. That is approximate nearest neighbour search, and it is the subject of note 10.

36. Building It: the Brute Force Lab

The lab is a command line program, written three times. There is no server and no model call. It has four parts that match this note:

A few decisions worth copying:

37. The Code, Side by Side

The full projects are on the code page:

Browse the code for this note, or open src/FDE/code/09-brute-force-vector-search/ on GitHub. The README there has the run and test commands for each version.

37.1 The pruning step in three languages

The heart of the k-d tree search is the same few lines everywhere:

double gap = query[node.axis()] - node.point().coords()[node.axis()];
Node near = gap < 0 ? node.left() : node.right();
Node far = gap < 0 ? node.right() : node.left();

visit(near, query, search);          // the query's own side first
if (gap * gap < search.bestSquared) {
    visit(far, query, search);       // only if the far side could still win
}

const gap = query[node.axis] - node.point.coords[node.axis];
const near = gap < 0 ? node.left : node.right;
const far = gap < 0 ? node.right : node.left;

visit(near, query, search);          // the query's own side first
if (gap * gap < search.bestSquared) {
  visit(far, query, search);         // only if the far side could still win
}

gap = search.query[node.axis] - node.point.coords[node.axis]
near, far = (node.left, node.right) if gap < 0 else (node.right, node.left)

self._visit(near, search)            # the query's own side first
if gap * gap < search.best_squared:
    self._visit(far, search)         # only if the far side could still win

gap is how far the query sits from the split line. Its sign tells which side the query is on: below zero means left. The query's own side is the near side, so it is searched first.

37.2 Where to look in the code

The tests check the claims this note makes: the heap gives the same top 10 as sorting every score, a search makes exactly N comparisons and N x D multiply-adds, 1,000,000 vectors of 1,536 numbers take 6,144,000,000 bytes, the two tea stall searches follow the paths in sections 29 and 30, the k-d tree agrees with brute force on random data, and the tree visits a small share of points in 2D but most of them in 32D.

37.3 What this demo leaves out on purpose

Key Takeaways

• A normal database can store vectors. The hard part is searching them by similarity, not storing them.
• Normal queries ask "which rows match this condition?". Vector search asks "which stored vectors are closest to this one?", and the answer is a ranking.
• The simplest vector database is three steps: store id, vector and metadata; embed the query with the same model; compare with every vector and keep the top K.
• K is just how many nearest neighbours you want back. KNN is the search that returns them.
• Brute force is exact. It always finds the true top K because it checks everything.
• Its cost is O(N x D). 1,000,000 vectors of 1,536 numbers is about 1.54 billion multiply-adds per query, and 6.14 GB of raw float32 numbers before ids, metadata and copies.
• Moving vectors to disk saves memory but makes each scan slower.
• A size K min heap keeps the top K in about N log K work without sorting everything.
• Normal indexes like B-trees are fast because order lets them skip most of the data. One dimension has that order. Two or more do not.
• A k-d tree splits space one axis at a time and prunes branches whose split line is further away than the best answer so far.
• Pruning works for a query far from the split lines in low dimensions. It fails near a line, and it fails almost everywhere in high dimensions.
• In high dimensions even the nearest point is far away, so the tree ends up visiting nearly every node. The open question for note 10 is how to look at only a small share of vectors and still find answers that are very close to the true nearest ones.