HNSW：分层可导航小世界图
NSW（Navigable Small World）基础
小世界网络理论
小世界网络两个特性：
聚类性：邻居之间互相连接，形成局部团
短路径：任意两点之间有较短的路径
普通图：A → B → C → D → E（5步） 小世界图：A → B → E（2步）NSW 的构建
import random class NSWNode: def __init__(self, id, vector): self.id = id self.vector = vector self.neighbors = [] # 邻居列表 class NSW: def __init__(self, max_neighbors=6): self.nodes = {} self.max_neighbors = max_neighbors def insert(self, id, vector): """插入新节点""" node = NSWNode(id, vector) self.nodes[id] = node # 找到最近的几个已有节点作为邻居 candidates = list(self.nodes.values()) if len(candidates) > 1: nearest = self._find_nearest(vector, candidates, k=self.max_neighbors) node.neighbors = nearest # 反向链接：让邻居也指向新节点 for neighbor_node in nearest: if len(neighbor_node.neighbors) < self.max_neighbors: neighbor_node.neighbors.append(node) def _find_nearest(self, vector, candidates, k): """找到最近的 k 个候选""" distances = [] for cand in candidates: d = self._distance(vector, cand.vector) distances.append((cand, d)) distances.sort(key=lambda x: x[1]) return [c for c, d in distances[:k]] def _distance(self, v1, v2): return sum((a - b) ** 2 for a, b in zip(v1, v2)) ** 0.5 def search(self, query, k=5): """搜索最近的 k 个向量""" # 随机选一个节点开始 start = random.choice(list(self.nodes.values())) # Greedy search：沿着最临近的方向走 current = start best_dist = self._distance(query, current.vector) while True: # 找当前节点邻居中比它更近的 better = None for neighbor in current.neighbors: d = self._distance(query, neighbor.vector) if d < best_dist: best_dist = d better = neighbor if better is None: break # 无法再近，停止 current = better # 此时 current 是局部最优 # 需要搜索更多起点找全局最优 results = [current] # 从多个起点搜索，取最优 for _ in range(5): start = random.choice(list(self.nodes.values())) candidate = self._greedy_search(start, query) results.append(candidate) # 排序返回最近的 k 个 results.sort(key=lambda n: self._distance(query, n.vector)) return results[:k] def _greedy_search(self, start, query): """从某个节点开始的贪心搜索""" current = start best_dist = self._distance(query, current.vector) while True: better = None for neighbor in current.neighbors: d = self._distance(query, neighbor.vector) if d < best_dist: best_dist = d better = neighbor if better is None: break current = better return currentHNSW：分层 NSW
HNSW 在 NSW 基础上增加了分层机制：
核心思想
高层：稀疏，跨度大，适合快速定位大致区域 底层：稠密，连接多，保证精度
HNSW 结构：
Layer 2: ●━━━━━━━━━━━━● ← 只有少量节点，跨度大 ┃ Layer 1: ●━●━━●━━●━━●━━●━● ← 中等密度 ┃ Layer 0: ●● ●● ●● ●● ●● ●● ← 最稠密，包含所有节点搜索过程（从上层开始）
def hnsw_search(query, top_k=5): """HNSW 搜索：从顶层开始，逐层向下""" # Step 1: 从顶层开始，找一个局部最优节点 # 顶层只有少量节点，快速定位大概位置 current = entry_points_at_top_layer current = greedy_search_in_layer(current, query, layer=TOP) # Step 2: 下降到下一层，继续搜索 for layer in range(TOP - 1, -1, -1): # 在这一层继续从 current 出发贪心搜索 while True: better_found = False for neighbor in current.neighbors[layer]: if distance(query, neighbor) < distance(query, current): current = neighbor better_found = True if not better_found: break # 当前层搜索完成后，作为下一层的起点 entry_point = current # Step 3: 在底层收集更多候选 candidates = [current] # 用优先队列维护最近的候选 # 继续搜索直到无法找到更近的节点 # Step 4: 返回最近的 top_k return get_top_k(candidates, query, k=top_k)构建过程（从底层向上）
def hnsw_insert(node, layer): """ HNSW 插入： - 随机决定节点出现在哪些层（越高层概率越低） - 从顶层插入，逐层向下 """ # 决定节点的最大层（随机，指数衰减概率） max_layer = get_random_layer(probability=0.5) # 概率递减 # 从最高层开始插入 current = entry_point[max_layer] for l in range(max_layer, -1, -1): # 在这一层找到最近邻居 neighbors = greedy_search(node.vector, layer=l) # 选择前 M 个作为邻居 node.neighbors[l] = neighbors[:MAX_M] # 更新邻居的反向链接 for neighbor in neighbors[:MAX_M]: if len(neighbor.neighbors[l]) < MAX_M: neighbor.neighbors[l].append(node) # 下一层的起点是这一层找到的最近节点 current = neighbors[0] if neighbors else current关键参数
# HNSW 参数说明 M = 16 # 每层每个节点的最多连接数 # M 越大，精度越高，但内存占用越大、构建越慢 # M=16：推荐默认 # M=8：内存受限场景 efConstruction = 200 # 构建时搜索范围 # efConstruction 越大，构建质量越高，但越慢 # 推荐：100-200 efSearch = 64 # 搜索时搜索范围 # efSearch 越大，精度越高，但越慢 # 推荐：50-200 max_level = 16 # 最大层数（自动计算）M 对精度和内存的影响
| M | 内存占用 | 构建速度 | 搜索精度 |
|---|---|---|---|
| 8 | 低 | 快 | 中 |
| 16 | 中 | 中 | 高 |
| 32 | 高 | 慢 | 很高 |
HNSW vs IVF 对比
| 特性 | HNSW | IVF |
|---|---|---|
| 搜索速度 | 极快 | 快 |
| 构建速度 | 慢 | 中等 |
| 内存占用 | 大 | 中等 |
| 搜索精度 | 高 | 中等 |
| 动态插入 | 较慢（影响多层） | 快（只需更新局部） |
| 适用规模 | 1亿+ | 1000万 |
| 参数复杂度 | 中（M, ef） | 低（nlist, nprobe） |
什么时候选 HNSW？
选择 HNSW 的场景： - 延迟要求极低（<10ms） - 数据量在千万级以上 - 数据相对稳定（插入不频繁） - 内存充裕 选择 IVF 的场景： - 数据量中等（百万-千万） - 内存有限 - 需要频繁插入/删除 - 需要精确召回面试常问
Q: HNSW 的分层思想是什么？
A:
高层：节点稀疏，连接跨度大，快速定位大致区域
低层：节点稠密，连接多，保证最终精度
搜索时从顶层开始，逐层向下精确定位
Q: HNSW 和 NSW 的区别？
A:
NSW：单层图，贪心搜索可能陷入局部最优
HNSW：多层结构，从高层快速定位，再逐层向下
Q: efConstruction 和 efSearch 是什么？如何调参？
A:
efConstruction：构建索引时搜索范围，越大构建质量越高但越慢
efSearch：搜索时搜索范围，越大搜索精度越高但越慢
调参建议：efConstruction=100-200，efSearch=50-200，从大到小实验
Q: HNSW 的缺点是什么？
A:
内存占用大（每条向量需要额外存储邻居指针）
构建慢（需要计算多层连接）
动态插入效率低（插入可能影响多层）
参数调优复杂（M, ef两个参数）