📚 课程目录第3章向量索引算法

3. 向量索引算法：从暴力搜索到工业级方案

向量索引，说白了就是给高维数据找个快速检索的办法。我刚开始接触这个领域时，觉得不就是个搜索嘛，能有多复杂？直到第一次在千万级数据集上跑KNN，等了半小时没出结果……嗯，从那以后我再也不敢小看索引算法了。

这一章，我们从头捋一遍主流算法。从最朴素的暴力搜索，到工业界最爱的HNSW和IVF，再到压缩大杀器PQ量化。你理解透这些，向量数据目录的底座就算打牢了。

  核心观点：没有完美的算法，只有适合场景的算法。选型时要在召回率、查询速度、内存占用之间做权衡。

3.1 暴力搜索（KNN）—— 最朴素，也最实在

KNN，全称K-Nearest Neighbors。原理简单到令人发指：算一遍所有向量与查询向量的距离，排个序，取前K个。

伪代码长这样：

def knn_search(query, vectors, k):
    distances = []
    for i, vec in enumerate(vectors):
        dist = euclidean_distance(query, vec)
        distances.append((dist, i))
    distances.sort(key=lambda x: x[0])
    return distances[:k]

复杂度是O(n*d)，n是向量数量，d是维度。数据量一上来，这玩意儿就扛不住了。我曾在500万条128维向量上跑KNN，单次查询耗时超过200毫秒——这在生产环境基本不可用。

避坑：KNN虽然召回率100%，但千万别用在实时检索场景。它更适合做基准测试，或者数据量小于1万的小型系统。

3.2 近似最近邻搜索（ANN）—— 用精度换速度

ANN的核心思想很简单：我不找最近的，我找“差不多最近”的。你想想看，用户真的在乎第1名和第5名的区别吗？大多数场景下，召回率95%以上就够用了。

ANN家族里，最出名的两个流派就是HNSW和IVF。下面我们逐个拆解。

3.3 HNSW算法详解—— 图结构里的高速公路

HNSW（Hierarchical Navigable Small World）是我个人在生产中用得最多的算法。它的本质是：构建多层图结构，上层是“高速公路”，下层是“乡间小路”。

搜索时，先从顶层开始，快速定位到大致区域，然后逐层往下细化。这个过程有点像你在地图上找一家餐厅——先看城市，再看区，最后看街道。

核心参数有三个：

参数	含义	典型值	影响
M	每个节点的最大连接数	16-64	M越大，召回越高，内存越大
ef_construction	构建时的动态候选集大小	200-500	越大构建越慢，但图质量越好
ef_search	搜索时的动态候选集大小	50-200	越大召回越高，查询越慢

我的经验：M设32，ef_construction设400，ef_search设100，这个组合在大多数场景下表现均衡。我曾经在一个电商推荐项目中用这套参数，召回率稳定在98%以上，单次查询耗时不到5毫秒。

HNSW的优点是召回率高、查询速度快。缺点也很明显——内存占用大。每个节点要存M个邻居的ID，1000万条128维向量，光图结构就要吃掉几个GB的内存。

3.4 IVF算法详解—— 先聚类，再搜索

IVF（Inverted File Index）的思路完全不同。它先对向量空间做K-Means聚类，把空间划分成若干个Voronoi单元。搜索时，只查离查询点最近的几个单元里的向量。

流程是这样的：

训练阶段：用K-Means把数据集聚成nlist个簇，每个簇有一个中心向量。
索引阶段：把每个向量分配到最近的簇，建立倒排列表。
搜索阶段：计算查询向量到各簇中心的距离，选最近的nprobe个簇，只在这些簇里做KNN。

关键参数：

参数	含义	典型值	影响
nlist	聚类中心数量	100-4096	越多，搜索范围越小，但聚类开销越大
nprobe	搜索时探查的簇数量	10-100	越大召回越高，查询越慢

注意：nprobe设得太小，召回率会断崖式下跌。我曾经在一个项目中把nprobe从20降到5，召回率直接从95%掉到了72%——边界上的向量全丢了。

IVF的优势是内存占用低，适合超大基数数据集。缺点是召回率对参数敏感，而且聚类训练本身需要时间。

3.5 PQ量化技术—— 把向量压缩到十分之一

PQ（Product Quantization）不是搜索算法，而是一种压缩技术。它的思路是把高维向量拆成若干子向量，对每个子空间独立做量化。

举个例子：一个128维的向量，拆成8个16维的子向量。每个子向量用K-Means聚成256个中心点（8bit编码）。这样，原来需要128×4=512字节的向量，压缩后只需要8个字节。

压缩比是64:1。你想想看，1亿条向量，原来要50GB，压缩后不到1GB。

PQ的搜索过程分两步：

离线量化：对每个子空间做聚类，生成码本。每个向量用码本中的中心点ID表示。
在线搜索：用对称或非对称距离计算，在压缩后的空间里做近似搜索。

  关键点：PQ通常不单独使用，而是作为IVF或HNSW的“加速器”。比如IVF+PQ，先用IVF缩小搜索范围，再用PQ做快速距离计算。这是Faiss中IndexIVFPQ的核心思路。

我个人的建议是：如果内存是瓶颈，优先上PQ。如果精度是瓶颈，优先上HNSW。如果两者都要……嗯，那就IVF+HNSW+PQ三层嵌套，但这需要非常精细的参数调优。

3.6 算法选型对照表

算法	召回率	查询速度	内存占用	适用场景
KNN	100%	极慢	低	基准测试、小数据集
HNSW	95-99%	极快	高	高精度、中等数据量
IVF	85-95%	快	中	超大基数、内存敏感
IVF+PQ	80-90%	快	极低	海量数据、内存受限

最后说一句：没有银弹。我在不同项目里用过HNSW、IVF、PQ的各种组合，每次选型都要根据数据规模、硬件配置、精度要求重新权衡。你把这些原理吃透了，选型时心里就有底了。