向量索引原理

问题

向量数据库是如何实现高效的相似度搜索的？常见的向量索引算法有哪些？

答案

一、相似度度量

在理解向量索引之前，先了解如何衡量两个向量的相似程度。

余弦相似度（Cosine Similarity）

衡量两个向量方向的相似程度，不受向量长度影响。

\text{cosine}(\vec{a}, \vec{b}) = \frac{\vec{a} \cdot \vec{b}}{|\vec{a}| \times |\vec{b}|}

值域：[-1, 1]，1 表示完全相同，0 表示正交，-1 表示完全相反
最常用：在 NLP/Embedding 场景中，语义相似度通常用余弦相似度

欧氏距离（L2 Distance）

衡量两个向量在空间中的直线距离。

L_2(\vec{a}, \vec{b}) = \sqrt{\sum_{i=1}^{n}(a_i - b_i)^2}

值域：[0, +∞)，越小越相似
适合向量已归一化的场景

内积（Inner Product / Dot Product）

\text{IP}(\vec{a}, \vec{b}) = \sum_{i=1}^{n} a_i \times b_i

如果向量已归一化（模为 1），内积等价于余弦相似度
用于推荐系统中的打分排序

度量方式	值域	含义	适用场景
余弦相似度	`[-1, 1]`	方向相似度	语义搜索（最常用）
欧氏距离	`[0, +∞)`	空间距离	归一化向量
内积	`(-∞, +∞)`	投影长度	推荐系统

二、暴力搜索的瓶颈

最简单的方法是遍历所有向量，逐一计算相似度并排序。时间复杂度 $O(n \times d)$ （n 为向量数，d 为维度）。

当数据量达到百万级以上时，暴力搜索延迟可能达到秒级，无法满足在线服务需求。因此需要 ANN（Approximate Nearest Neighbor，近似最近邻） 算法——牺牲少量精度换取数量级的速度提升。

三、主要向量索引算法

1. IVF（Inverted File Index，倒排文件索引）

核心思想：先用 K-Means 将向量空间聚成若干簇（Cluster），查询时只搜索最接近的几个簇。

关键参数：

nlist：聚类数量（通常 $\sqrt{n}$ 到 $4\sqrt{n}$ ）
nprobe：查询时搜索的簇数量（越大越精确，越慢）

搜索开销：从 $O(n)$ 降到约 $O(\frac{n \times \text{nprobe}}{\text{nlist}})$

2. HNSW（Hierarchical Navigable Small World，分层可导航小世界图）

核心思想：构建多层图结构，上层稀疏用于快速定位，下层稠密用于精确搜索。类似于「跳表」的思想。

搜索过程：

从最高层的入口节点开始
在当前层贪心搜索最近邻
找不到更近的节点时，下降到下一层
在最底层找到精确的 Top-K 近邻

关键参数：

M：每个节点的最大连接数（影响图的密度，通常 8~64）
efConstruction：建图时的搜索宽度（越大建图越慢但质量越高）
efSearch：查询时的搜索宽度（越大越精确，越慢）

优势：

查询速度极快，通常 < 10ms
召回率高（> 95%）
支持动态增删

劣势：

内存占用大（需要存储图结构）
建图时间长

HNSW 是当前最流行的向量索引

几乎所有主流向量数据库（Milvus、pgvector、Qdrant、Pinecone）都以 HNSW 作为默认或首选索引。它在查询速度和召回率之间取得了最佳平衡。

3. PQ（Product Quantization，乘积量化）

核心思想：将高维向量分割成多个子空间，每个子空间用聚类中心（码本）近似表示，大幅压缩存储。

原始向量 (128维):
[0.23, -0.15, 0.87, ..., 0.42]  → 128 × 4B = 512 字节

PQ 压缩后 (分8段，每段256个聚类中心):
[23, 156, 42, 200, 15, 88, 201, 77]  → 8 × 1B = 8 字节

压缩比：64:1

搜索过程：

将查询向量也分段
预计算查询向量每段到所有聚类中心的距离（距离查找表）
用查找表快速计算近似距离

适合场景：内存有限但数据量极大的场景（如十亿级向量）

4. IVF-PQ（组合索引）

将 IVF 和 PQ 结合：先用 IVF 缩小搜索范围，再用 PQ 压缩存储和加速计算。

查询 → IVF 定位簇 → PQ 近似计算距离 → 返回 Top-K

5. Flat（暴力搜索）

不建索引，精确搜索。适合数据量小（< 10 万）的场景。

四、索引算法对比

算法	搜索速度	召回率	内存占用	建索引速度	适合数据量
Flat	慢	100%	低	无需建索引	< 10万
IVF	中	90-99%	低	快	百万级
HNSW	快	95-99%	高	慢	百万~千万
PQ	快	80-95%	极低	中	亿级
IVF-PQ	快	85-95%	低	中	亿级

五、选型建议

常见面试问题

Q1: HNSW 为什么那么快？

答案：

HNSW 快的核心原因是多层跳跃 + 贪心搜索：

多层图：高层节点稀疏，一跳可以跨越大量节点，快速逼近目标区域（类似跳表）
贪心策略：每一步都走向当前最近邻，避免遍历无关区域
小世界特性：图的平均路径长度为 $O(\log n)$

搜索复杂度约 $O(\log n)$ ，远优于暴力搜索的 $O(n)$ 。

Q2: 向量索引的召回率（Recall）是什么？

答案：

召回率衡量 ANN 算法找到真正最近邻的比例：

\text{Recall@K} = \frac{|\text{ANN 返回的 K 个结果} \cap \text{真正的 K 个最近邻}|}{K}

例如 Recall@10 = 0.95 表示前 10 个结果中有 9.5 个是真正的最近邻。

生产环境通常要求 Recall > 95%。

Q3: HNSW 和 IVF 的核心区别？

答案：

对比	HNSW	IVF
数据结构	多层图	聚类 + 倒排
搜索策略	图上贪心遍历	先定位簇，再暴力搜索
内存	高（需存图结构）	低
动态增删	支持增加	增加需重新聚类
查询速度	更快	较快
适合场景	对延迟敏感的在线服务	大数据量、内存有限

Q4: PQ 量化为什么能压缩向量？

答案：

原理：将 128 维向量分成 8 段（每段 16 维），对每段做 K-Means 聚类（256 个中心），用 1 个字节（0~255）的聚类 ID 代替 16 维浮点数（64 字节）。

压缩比 = 原始大小 / 压缩后大小 = (128 × 4B) / 8B = 64 倍。

代价是精度下降，因为用聚类中心近似了原始向量。

Q5: 如何选择向量索引的参数？

答案：

以 HNSW 为例：

参数	推荐值	影响
`M`	16~64	越大召回越高，内存越大
`efConstruction`	100~500	越大建图质量越好，速度越慢
`efSearch`	50~200	越大搜索越精确，延迟越高

调参策略：先用默认值，在 Recall 和延迟之间做 A/B 测试，找到业务可接受的平衡点。

问题​

答案​

一、相似度度量​

余弦相似度（Cosine Similarity）​

欧氏距离（L2 Distance）​

内积（Inner Product / Dot Product）​

二、暴力搜索的瓶颈​

三、主要向量索引算法​

1. IVF（Inverted File Index，倒排文件索引）​

2. HNSW（Hierarchical Navigable Small World，分层可导航小世界图）​

3. PQ（Product Quantization，乘积量化）​

4. IVF-PQ（组合索引）​

5. Flat（暴力搜索）​

四、索引算法对比​

五、选型建议​

常见面试问题​

Q1: HNSW 为什么那么快？​

Q2: 向量索引的召回率（Recall）是什么？​

Q3: HNSW 和 IVF 的核心区别？​

Q4: PQ 量化为什么能压缩向量？​

Q5: 如何选择向量索引的参数？​

相关链接​

问题

答案