NSW (Navigable Small Worlds) Index

NSW is the graph-based building block of HNSW: it starts from one or more entry points and greedily follows neighbors closer to the query vector. This chapter implements it as the last fully specified checkpoint in the C++ course. The starter represents the graph as layers_[0] inside HNSWIndex so the next, optional chapter can add hierarchy.

Complete the previous chapters first. You will likely modify:

src/include/storage/index/hnsw_index.h
src/storage/index/hnsw_index.cpp

Related readings:

• Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs
• HNSW in Pinecone’s Faiss guide

Search One Layer

One Entry Point and One Neighbor

The first diagram shows an NSW graph in two dimensions. The highlighted red vertex is the entry point, and the query vector is elsewhere in the space. Search begins at the entry point because the graph does not provide a global ordering or a centroid that points directly to the answer.

Compare the query with every neighbor of the current vertex and move to a neighbor that is closer. Repeating this greedy step walks through the graph toward the query.

The walk stops when none of the current vertex’s neighbors is closer. Because it explores only graph edges, it can stop at a local minimum instead of the globally nearest vector; NSW is therefore an approximate index.

Multiple Entry Points and k Neighbors

Now ask for three neighbors while starting from two entry points. Searching multiple regions reduces the chance that one poorly placed entry point traps the walk in the wrong part of the graph. For k-nearest-neighbor search, maintain:

• C, a min-heap of candidates to explore, with the nearest candidate on top;
• W, a max-heap of the best visited candidates, with the worst retained result on top; and
• visited, a set that prevents repeated graph expansion.

Seed all three structures from both entry points. The next diagram shows the initial state before any vertex is expanded.

The nearest item in C is entry point 1. Pop it, mark its unseen neighbors as visited, add promising neighbors to C and W, and keep only the three best visited candidates in W.

The next candidate is the highlighted vertex below. Its neighbors have already been visited, so expanding it does not add anything to either queue.

Entry point 2 is now the nearest unexplored candidate. Expanding it adds candidates from a different part of the graph, which is the benefit of seeding the search from more than one location.

Continue popping the nearest candidate and updating W. Even when many vertices have been visited, W retains only the three closest ones found so far.

Eventually the nearest candidate left in C is farther from the query than the worst result in the full W. No queued candidate can improve the result, so the search stops.

C = entry_points as a min-heap by distance
W = unique entry_points as a max-heap by distance
visited = unique entry_points

while C is not empty:
    candidate = C.pop_nearest()
    if W is full and distance(candidate) > distance(W.worst):
        break

    for neighbor in candidate.neighbors:
        if neighbor is already visited:
            continue
        mark neighbor visited
        if W is not full or distance(neighbor) < distance(W.worst):
            C.push(neighbor)
            W.push(neighbor)
            trim W to the search width

return W sorted from nearest to farthest

Why Multiple Entry Points Matter

If the same graph asks for two neighbors but starts only from entry point 1, the search can reach the state below and stop: every remaining candidate in C is worse than both results in W, even though the graph contains closer vertices in another region. A second entry point seeds that region directly; it does not guarantee exact search, but it reduces this failure mode.

Course rules for NSW::SearchLayer:

• return an empty vector for limit = 0, no entry points, or an empty layer;
• ignore duplicate entry-point IDs and never visit a vertex more than once;
• use dist_fn_ for every comparison; and
• return at most limit vertex IDs, sorted from nearest to farthest.

Insert into the Graph

To insert the highlighted new vector, search the existing graph with width ef_construction, then select its nearest m candidates as neighbors. The first diagram shows those selected connections.

NSW::Connect creates an undirected edge between the new vertex and each selected neighbor. Those new edges can put an existing vertex over the layer’s m_max_ degree cap, as in the second diagram.

For every overfull vertex, re-select its nearest m_max_ neighbors. The third diagram marks the edges that survive this pruning decision.

Finally, remove every rejected edge from both endpoints. The last diagram is the resulting graph; updating only the overfull vertex would leave one-sided edges and break the undirected-graph invariant.

Course rules for insertion:

• The first vertex is added without searching or connecting.
• Do not create self-edges or duplicate edges.
• Keep edges_[a] and edges_[b] symmetric after both connection and pruning.
• SelectNeighbors returns at most m unique IDs ordered by dist_fn_.
• Add the new vertex to the layer exactly once.

The starter parameters mean:

• m_: how many neighbors a new vertex selects;
• ef_construction_: the insertion-search width;
• ef_search_: the query-search width;
• m_max_: the upper-layer degree cap reserved for HNSW; and
• m_max_0_: the layer-0 degree cap. The starter derives it as m_ * m_ and assigns it to layers_[0].m_max_.

Require m > 1, ef_construction >= m, and ef_search >= 1. The first condition also keeps the starter’s m_l_ = 1 / log(m) finite for the optional HNSW extension.

For a SQL LIMIT k, search layer 0 with width max(k, ef_search_), then select and return the nearest k RIDs. This ensures that a request for more than ef_search_ rows can still return k rows, while a larger ef_search_ can improve recall.

Verify the Checkpoint

From bustub-vectordb/build, run:

make -j8 sqllogictest
./bin/bustub-sqllogictest ../test/sql/vector.05-hnsw.slt --verbose

Confirm that results are sorted by distance, inserts after index construction are searchable, and the LIMIT 5 query can return five rows even though the test index uses ef_search = 3. Random build order can change tie ordering.

<main>:1
CREATE TABLE t1(v1 VECTOR(3), v2 integer);
----
Table created with id = 24	

<main>:4
INSERT INTO t1 VALUES (ARRAY [0.0, 1.0, 1.0], 0), (ARRAY [1.0, 1.0, 1.0], 1), (ARRAY [2.0, 1.0, 1.0], 2), (ARRAY [3.0, 1.0, 1.0], 3), (ARRAY [4.0, 1.0, 1.0], 4), (ARRAY [5.0, 1.0, 1.0], 5);
----
0	

<main>:7
CREATE INDEX t1v1hnsw ON t1 USING hnsw (v1 vector_l2_ops) WITH (m = 3, ef_construction = 3, ef_search = 3);
----
Index created with id = 0 with type = VectorHNSW	

<main>:10
EXPLAIN (o) SELECT v1, v2, ARRAY [1.0, 1.0, 1.0] <-> v1 as distance FROM t1 ORDER BY ARRAY [1.0, 1.0, 1.0] <-> v1 LIMIT 3;
----
=== OPTIMIZER ===
Projection { exprs=["#0.0", "#0.1", "l2_dist([1.000000,1.000000,1.000000], #0.0)"] }
  VectorIndexScan { index_oid=0, index_name=t1v1hnsw, table_oid=24, table_name=t1 base_vector=[1.000000,1.000000,1.000000], limit=3 }
	

<main>:13
SELECT v1, v2, ARRAY [1.0, 1.0, 1.0] <-> v1 as distance FROM t1 ORDER BY ARRAY [1.0, 1.0, 1.0] <-> v1 LIMIT 3;
----
[1,1,1]	1	0.000000	
[2,1,1]	2	1.000000	
[0,1,1]	0	1.000000	

<main>:16
INSERT INTO t1 VALUES (ARRAY [-1.0, 1.0, 1.0], -1), (ARRAY [-2.0, 1.0, 1.0], -2), (ARRAY [-3.0, 1.0, 1.0], -3), (ARRAY [-4.0, 1.0, 1.0], -4);
----
0	

<main>:19
SELECT v1, v2, ARRAY [1.0, 1.0, 1.0] <-> v1 as distance FROM t1 ORDER BY ARRAY [1.0, 1.0, 1.0] <-> v1 LIMIT 5;
----
[1,1,1]	1	0.000000	
[2,1,1]	2	1.000000	
[0,1,1]	0	1.000000	
[3,1,1]	3	2.000000	
[-1,1,1]	-1	2.000000	

Also compare an NSW query with SET vector_index_method=none. Exact Top-N is the oracle for recall, not a requirement that every approximate result match.

Prediction: If the graph has two disconnected components and every entry point is in the first component, can SearchLayer return a vertex from the second? Explain why the visited and stop-condition code cannot repair missing connectivity.

You are done when you can trace one vertex ID through vertices_, layers_[0].edges_, rids_, and the table lookup, and explain what would break if pruning removed only one side of an undirected edge.

Optional Extensions

• Implement the paper’s heuristic neighbor-selection rule.
• Add deletion and update support.
• Persist the graph after defining a stable on-disk layout.

Your feedback is greatly appreciated. Join our Discord community.
Found an issue? Open an issue or pull request at github.com/skyzh/write-you-a-vector-db.
write-you-a-vector-db © 2024-2026 by Alex Chi Z. All Rights Reserved.