HNSW 近邻检索HNSW approximate nearest-neighbor search
在 HNSW 图索引中先沿高层逼近目标，再在底层扩展候选近邻。
- 核心约束
- 候选集、已访问集合和保留结果必须与距离计算及终止条件一致。
- 适用问题
- 高召回率的近似向量检索。
- 边界与取舍
- 这是图索引上的检索过程；增加搜索宽度通常提高召回并增加成本，仍不保证精确最近邻。
时间与空间#
q 为本次距离计算次数，d 为向量维度，s 为队列操作数，H 为实际堆大小上限。
- 时间复杂度
- 稠密距离工作 ，堆维护约
- 辅助空间
- 候选集、结果集和已访问标记；取决于实现
q、s 随数据分布、图构建和 efSearch 变化，不能对一般输入保证 。结果集的 efSearch 限制不一定也限制待扩展堆大小；已访问数组可能按全索引大小预分配，高召回率通常需要访问更多候选。
工程中的应用#
1 个案例 · 附源码HNSW 从稀疏上层快速定位区域，再在底层扩大候选搜索。
附源码片段 · 检索与计算
基础原理参考资料
Malkov & Yashunin · HNSW分层贪心搜索、候选扩展与近似搜索的参数。
Faiss 1.9 · HNSW search距离计算、候选队列与 visited 标记的实际路径。