向量检索引擎核心原理：HNSW 索引与近似最近邻检索的工程实战

在 RAG（检索增强生成）成为大模型应用的标配之后，"向量数据库"几乎成了 AI 基础设施的代名词。但大多数工程师只停留在 collection.insert() 和 query() 的 API 层面，对底层检索算法一知半解——一旦线上出现召回率下跌、查询延迟抖动或内存暴涨，便无从下手。本文从工程视角拆解向量检索的核心：为什么暴力检索不可行，以及当今主流引擎（Milvus、Qdrant、Weaviate、pgvector）共同依赖的 HNSW 图索引究竟如何工作。

一、问题定义：从 O(N·d) 说起

给定 N 个 d 维向量和一条查询向量，找出最近的 k 个。最直接的"暴力检索"（Flat Index）需要计算查询与每个向量的距离，复杂度 O(N·d)。当 N = 1000 万、d = 768（BGE 文本嵌入维度）时，单次查询就是近 80 亿次浮点乘法。即便用 SIMD 和 GPU 优化，在毫秒级 SLA 下也不可接受。

更麻烦的是"维度灾难"：高维空间里所有点彼此距离趋于均匀，基于空间划分的传统索引（KD-Tree、Ball-Tree）在 d > 20 后几乎退化成线性扫描。因此，向量检索必须放弃"精确"，转向近似最近邻（ANN）——用可控的召回率损失，换取几个数量级的加速。

二、两条主流路线：IVF 与图索引

ANN 领域有两条经过工业验证的路线。

IVF（倒排文件） 用一个粗粒度量化器（如 k-means）把空间切成 nlist 个簇，查询时只搜索距离最近的若干簇（nprobe 个）。它像图书馆的分类书架：先找对大类，再在类内细翻。IVF 的内存和召回都很容易调，但"找对大类"这一步本身会丢召回——尤其当查询恰好落在簇边界时。

图索引（以 HNSW 为代表） 则不划分空间，而是把向量组织成一张近邻图：每个节点连向它的近邻，查询从入口点出发，在图上"贪心"地走向更近的节点，直到局部最优。它的优势是在高召回下依然保持极低延迟，代价是更高的内存占用和更复杂的构建过程。

HNSW（Hierarchical Navigable Small World，分层可导航小世界图）是图索引的事实标准，由 Malkov 等人在 2016 年提出。下面我们直接看它的结构与代码。

三、HNSW 的结构：概率跳表式的多层图

HNSW 的核心直觉来自跳表（Skip List）：建一张多层图，第 0 层包含所有节点，越往上节点越稀疏，顶层只有极少数"高速公路"节点。查询时从顶层开始做贪心搜索，快速逼近目标区域，再逐层下降做精细搜索。这种"先粗后细"的层次化，把复杂度从 O(N) 降到 O(log N)。

每个新插入的节点会被随机分配到若干层（层数 l 由几何分布决定：P(l) 随层指数衰减），并只连接它所在层及以下的近邻。连接数由参数 M 控制——M 越大，图越"稠密"，召回更高但内存和构建成本也更高。

下面是一段可运行的最小 HNSW 实现（为可读性省略了部分启发式剪枝），足以说明插入与查询的精髓：

import numpy as np
import heapq

def cosine_dist(a, b):
    return 1 - np.dot(a, b) / (np.linalg.norm(a) * np.linalg.norm(b) + 1e-9)

class HNSW:
    def __init__(self, M=8, ef_construction=64, ef_search=32):
        self.M = M
        self.efC = ef_construction
        self.efS = ef_search
        self.layers = [[]]          # 每层是节点索引列表
        self.graph = {}             # node -> {layer: [neighbors]}
        self.data = []

    def _random_level(self):
        l = 0
        while np.random.rand() < 0.5 and l < 16:
            l += 1
        return l

    def _search_layer(self, q, entry, layer, ef):
        # 贪心 + 候选集的近似搜索，返回近邻候选
        visited = set(entry)
        candidates = [(cosine_dist(q, self.data[e]), e) for e in entry]
        heapq.heapify(candidates)            # 小顶堆：最近优先
        result = []
        while candidates:
            dist, node = heapq.heappop(candidates)
            if result and dist > result[-1][0]:
                break
            result.append((dist, node))
            for nb in self.graph[node].get(layer, []):
                if nb not in visited:
                    visited.add(nb)
                    heapq.heappush(candidates,
                                   (cosine_dist(q, self.data[nb]), nb))
            if len(result) >= ef:
                break
        return [n for _, n in result]

    def insert(self, vec):
        vec = np.asarray(vec, dtype=float)
        idx = len(self.data)
        self.data.append(vec)
        self.graph[idx] = {}
        top = len(self.layers) - 1
        l = self._random_level()
        while l > top:                       # 扩展层
            self.layers.append([]); top += 1
        entry = [0] if self.data else []
        for layer in range(top, -1, -1):
            if layer > l:
                continue
            if not entry:
                entry = [idx]; continue
            near = self._search_layer(vec, entry, layer, self.efC)
            self.graph[idx][layer] = near[:self.M]
            for nb in self.graph[idx][layer]:
                self.graph[nb].setdefault(layer, [])
                if len(self.graph[nb][layer]) < self.M * 2:
                    self.graph[nb][layer].append(idx)
            entry = near[:1] or entry
        self.layers[l].append(idx)

    def query(self, q, k=5):
        q = np.asarray(q, dtype=float)
        entry = [n for layer in self.layers for n in layer][:1]
        for layer in range(len(self.layers) - 1, -1, -1):
            near = self._search_layer(q, entry, layer, self.efS)
            entry = near[:1] or entry
        return sorted(near, key=lambda n: cosine_dist(q, self.data[n]))[:k]

这段代码虽小，却抓住了 HNSW 的三个关键工程点：(1) 用候选集（ef）替代纯贪心，避免陷入局部最优；(2) 层数随机化保证图的小世界特性；(3) 每层只保留 M 个邻居，控制度数上限以抑制内存膨胀。

四、三个必须理解的生产参数

把 HNSW 用进生产，真正决定成败的是这三个旋钮：

• ef_search（查询候选集）：越大召回越高、延迟越大。线上调优本质是找"召回率-延迟"的拐点，而非一味拉满。多数场景 ef_search 取 32~128 即可。
• ef_construction（构建候选集）：越大索引质量越高，但构建越慢。批量建库时可以适当调大（如 200），换更好的检索质量。
• M（每层最大连接数）：典型值 8~32。M 越大召回上限越高，但也更吃内存——HNSW 的内存常是原始向量的数倍。

一个常被忽视的真相：HNSW 是内存索引。它把整张图驻留内存，单机内存往往成为规模上限。当数据量超过内存容量，就需要分片（sharding）或换用磁盘友好的索引（如 DiskANN 的 Vamana 图）。

五、工程选型：pgvector 还是专用引擎？

很多团队的第一反应是"上 Milvus"。但我的实战建议相反：先用 pgvector。如果你的主数据是关系型的，pgvector 让你在同一个事务里完成"按用户过滤 + 向量检索"，避免双写和数据不一致，运维成本也低一个量级。只有当满足以下任一条件，才值得引入专用向量数据库：

1. 向量规模超过千万且需要高 QPS 并发；
2. 需要复杂的混合检索（稠密 + 稀疏 BM25 + 重排序）；
3. 需要多租户隔离、量化压缩（PQ/SQ）等高级能力。

无论选哪个，永远在真实数据分布上做召回率-延迟基准测试，而不是轻信厂商 benchmark。文本嵌入的聚类特性与图像嵌入差异巨大，参数没有银弹。

六、结语

向量检索不是黑盒 API。理解 IVF 与图索引的取舍、吃透 HNSW 的层次结构与三个核心参数，你才能在召回率、延迟、内存三者间做出有依据的工程权衡。下一次线上向量检索出问题，希望你能直接从图的结构和参数入手，而不是盲调 ef_search。