向量数据库索引原理：HNSW 与 IVF 区别？

题目

向量数据库常用 HNSW 与 IVF 两类索引。请说明二者原理、查询性能与构建成本，以及如何选型。

参考答案

二者都是**近似最近邻搜索（ANN）**算法，用精度换速度，区别在于数据组织方式。

IVF（Inverted File，倒排索引）：

• 原理：先用 k-means 把向量空间聚成 $nlist$ 个簇，每个簇维护一个倒排表。查询时找最近的 $nprobe$ 个簇，在这些簇内暴力搜索。
• 参数：$nlist$（簇数）、$nprobe$（探测簇数）。$nprobe$ 越大越准越慢。
• 构建快、内存小，但 recall 上限受聚类质量限制。
• 适合大规模、对延迟要求不极致的场景。

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

• 原理：构建多层图，上层稀疏（长程连接）、下层密集（短程连接）。查询从顶层入口贪心下降，逐层细化到最底层。
• 参数：$M$（每层邻居数）、$efConstruction$（建图候选数）、$efSearch$（查询候选数）。
• 查询极快、recall 高，但构建慢、内存大（要存图结构）。
• 适合低延迟、高 recall 的在线检索。

对比表：

维度	IVF	HNSW
数据结构	倒排表	分层图
构建	快（聚类）	慢（建图）
内存	小	大（图结构）
查询速度	中	极快
Recall	中-高	高
适合	大规模、批量	在线、低延迟

进阶：

• IVF-PQ：IVF + 乘积量化压缩向量，用精度换内存，适合超大规模（亿级）。
• HNSW + PQ：图索引 + 向量压缩，兼顾速度与内存。
• DiskANN：磁盘友好型索引，超大规模低成本部署。

选型建议：

• 数据量小（< 100 万）、要低延迟 → HNSW。
• 数据量大（亿级）、可接受稍高延迟 → IVF-PQ。
• 需要过滤（按元数据）→ 选支持预过滤的索引（如 HNSW + filter）。

面试加分点：

• 指出 ANN 是”用少量精度损失换数百倍速度”，工业 RAG 几乎不用暴力搜索。
• HNSW 的”分层”灵感来自跳表（skip list），用空间换时间。
• 现代向量库（Milvus/Qdrant/Weaviate）多同时支持两者，按场景配置。

出处：Milvus 文档、Qdrant 文档、向量检索面经。