Build your own vector database
Building the index (Algorithm 1)·7 min

The insert algorithm

0 / 1

Algorithm 1 assembles everything you have built. To insert a new element q:

  1. Draw its level l (the seeded dice from Chapter 1).
  2. Descend from the current top layer down to l+1 with SEARCH-LAYER at ef = 1 — just walk toward q, no result set, to find a good entry point for the next phase.
  3. Wire edges from min(l, topLayer) down to 0: at each layer run SEARCH-LAYER at efConstruction, SELECT-NEIGHBORS from the results, add bidirectional edges, then for each new neighbor whose degree now exceeds Mmax (Mmax0 at layer 0) shrink its neighbor list.
  4. Promote q to entry point if l exceeds the current top layer.
Algorithm 1 skeleton
l <- assignLevel()
ep <- [entryPoint]
for lc from topLayer down to l+1:        // greedy descent, ef=1
  ep <- [ nearest of SEARCH-LAYER(q, ep, 1, lc) ]
for lc from min(topLayer, l) down to 0:  // wire edges, ef=efConstruction
  W   <- SEARCH-LAYER(q, ep, efConstruction, lc)
  nbs <- SELECT-NEIGHBORS(q, W, M)
  connect(lc, q, nbs, Mmax_for(lc))      // bidirectional + shrink
  ep  <- W
if l > topLayer: topLayer <- l; entryPoint <- q
Edges are bidirectional and capacity-bounded

When you add new ↔ neighbor, the neighbor may now exceed Mmax. You must re-select its neighborhood with the heuristic and possibly drop an old edge. Forgetting to shrink makes hub nodes with thousands of edges — slow and memory-blown. Shrinking with the heuristic (keeping pruned connections) is also what preserves layer-0 connectivity.

The heuristic testConnect + shrink a neighborhood