What you're building
You're building a mini Qdrant — a real vector database, in TypeScript, from scratch. The engine inside it is HNSW (Hierarchical Navigable Small World), the same graph index Qdrant, Pinecone, Weaviate, and FAISS ship. By the end you'll search a corpus of vectors at high recall while touching a tiny fraction of them per query, then add the three things that turn an index into a database: payload filtering, on-disk segments, and int8 quantization.
A skip list lets you binary-search a linked list by stacking express lanes on top. HNSW is a skip list in metric space: the top layers are sparse express lanes that teleport you near the answer; the bottom layer is the local street grid where you find it exactly.
The tower you will build
L2 (o) <- entry point, sparse express lane
|
L1 (o)--(o)----(o) <- fewer nodes, long hops
| | |
L0 (o)-(o)-(o)-(o)-(o)-(o)-(o) <- every node, the street grid
search: drop in at the apex, greedily walk downhill (= closer)
to the query, finishing with a wide search on layer 0.
Each chapter adds exactly one piece and earns one green check:
- Data structures — the two priority queues + the seeded level dice.
- SEARCH-LAYER — the greedy walk across one layer (Algorithm 2).
- SELECT-NEIGHBORS — which M candidates become edges (Algorithms 3 & 4).
- INSERT — assemble the graph (Algorithm 1).
- K-NN-SEARCH + recall — the payoff: recall under a comparison budget (Algorithm 5).
- Payload filtering — the Qdrant problem.
- Persistence — serialize a segment, reload it identically.
- Quantization — int8 vectors, 4x smaller, with rescoring.
- Capstone — the whole mini-Qdrant, end to end.