Faiss/HNSW 索引

用分层近邻图检索相似向量

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

v1.9.0检索与计算核验 2026-10-08

工程问题#

语义检索需要从大量向量寻找相似项,逐个精确计算距离可能超过延迟预算。

实际实现#

Faiss 维护多层邻接关系;搜索先在高层贪心接近目标,再在底层探索候选,efSearch 控制搜索范围。

处理流程#

  1. 从最高层入口开始
  2. 沿邻边寻找更近节点
  3. 逐层下降到密集底层
  4. 扩展候选并返回近邻结果

源码片段#

固定版本 · 原文摘录
faiss/impl/HNSW.cppv1.9.0 · L928–L945
查看原文件
928    //  greedy search on upper levels929    storage_idx_t nearest = entry_point;930    float d_nearest = qdis(nearest);931932    for (int level = max_level; level >= 1; level--) {933        HNSWStats local_stats =934                greedy_update_nearest(*this, qdis, level, nearest, d_nearest);935        stats.combine(local_stats);936    }937938    int ef = std::max(params ? params->efSearch : efSearch, k);939    if (bounded_queue) { // this is the most common branch940        MinimaxHeap candidates(ef);941942        candidates.push(nearest, d_nearest);943944        search_from_candidates(945                *this, qdis, res, candidates, vt, stats, 0, 0, params);
HNSW::search

从 entry_point 开始,在高层贪心更新最近节点,然后以该节点作为底层候选入口。ef 至少为 k,bounded_queue 分支用候选堆限制搜索范围。片段展示常见分支,后续代码另有无界候选队列路径;efSearch 是搜索宽度参数,不是精确召回保证。

CPPMIT

收益与取舍#

工程分析

带来的收益

  • 避免每次遍历全部向量
  • 可通过搜索参数调整召回与延迟

付出的代价

  • 图边需要额外内存,构建也有距离计算成本
  • 近似搜索不保证找到真实最近邻

可比较的选择

IndexFlat穷举可作为精确基线;数据较小时,图构建和额外内存未必值得。

版本与适用范围#

以 Faiss v1.9.0 CPU HNSW 为基线;不同存储后端可组合不同压缩方法,不将 HNSW 等同于向量压缩。

参考来源#

源码、官方文档与原始论文
01
HNSW 搜索实现

faiss/impl/HNSW.cpp · HNSW::search

源码v1.9.0
02
Faiss HNSW 索引入口

faiss/IndexHNSW.cpp · IndexHNSW::search / IndexHNSW::add

源码v1.9.0

相关实现与比较#

4 个相关案例
5 个匹配案例