You already know: embeddings, normalization and quantization (Embeddings); k-means (D3 Unsupervised learning); heaps and graphs (D1 Data structures); memory hierarchies and paging (D1 Operating systems); tombstones and compaction (Retrieval fundamentals exercise).
Why this matters for Atlas. Finding the nearest vectors exactly means comparing the query with every stored vector. That's fine for thousands of vectors and hopeless for hundreds of millions. Approximate nearest neighbour (ANN) indexes give up a little recall for orders of magnitude in speed and memory, and a vector database wraps them with what production needs: metadata filters, updates, deletes, persistence, replication and sharding. Picking and tuning one is a set of trade-offs you can measure. This lesson builds the three core index families from scratch.
1. Why exact search doesn't scale
The question. How expensive is "compare the query with everything"?
Start from nothing. Exact search does N dot products of dimension d per query, so cost grows linearly with both. Here it is measured on this machine and extrapolated: