HNSW 图索引Hierarchical navigable small-world index

用多层近邻图保存向量的导航关系：底层覆盖全部元素，高层保留更稀疏的子集。

常见操作#

n 为向量数，d 为向量维度，M 为每节点邻接上限的量级；q 为一次搜索计算距离的节点数；V、E 为各层顶点和边的总数。

操作	时间复杂度	条件与说明
新增向量	搜索插入位置 + 邻居筛选 / 反向连接	efConstruction、M、图形状与距离计算成本共同决定，不能统一保证 $O(\log n)$ 。
近邻查询	距离计算约 $O(qd)$ ，另计候选队列维护	稠密向量距离逐维计算；q 随 efSearch、数据分布和召回要求变化。
标记删除 / 物理移除	由实现的删除策略决定	标记删除不等于修复连通性；并非所有实现支持在线物理删除。
遍历图结构	$O(V+E)$	逐层访问邻接表，另计读取向量数据。

随机层高控制上层规模；M 若随数据增长，不能把图存储写成无条件 $O(n)$ 。

1 个案例 · 附源码

Faiss·HNSW 索引v1.9.0

HNSW 从稀疏上层快速定位区域，再在底层扩大候选搜索。

附源码片段 · 检索与计算

基础原理参考资料

Malkov & Yashunin · HNSW分层构图、近邻选择、参数与实验复杂度讨论。

hnswlib · Algorithm parametersM、efConstruction、ef 对内存和搜索质量的作用。