HNSW 图索引原理与参数调优

一、问题：暴力搜索为什么慢

假设你有一批高维向量，用户输入一个查询向量，要找最相似的 Top-K。

暴力搜索（Flat）：
  计算查询向量与所有候选向量的距离 → 排序 → 取 Top-K
  时间复杂度：O(N × D)，N=向量数量，D=向量维度
  耗时随 N 和 D 线性增长，具体数值取决于硬件、过滤条件和实现

这对于生产环境太慢了。需要近似最近邻（ANN）算法来加速。

二、ANN 的核心思想：搜索前先建索引

暴力搜索 = 不建索引，每次全量扫描
ANN 搜索 = 提前建好索引，搜索时走捷径

类比：
  暴力搜索 = 在图书馆一本一本翻找
  ANN 搜索 = 先查目录卡片（索引），按卡片指引去对应的书架

ANN 的核心权衡：精度 vs 速度。

• 精度 100% = 暴力搜索
• ANN = 用近似召回换查询加速
• 索引越激进，越可能更快，但越需要用评测集确认召回损失

三、HNSW 的三个核心概念

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

3.1 Small World Graph（小世界图）

小世界图是一种特殊的图结构，具有"六度分隔"特性：图中任意两个节点之间的路径都很短。

在一个好的小世界图中：
  任意两个节点 → 只需跳 3-6 步就能到达

  节点A → 节点C → 节点F → 节点Z
    ↑       ↑       ↑
  （每一步都更接近目标）

对于向量检索，图中每个节点是一个向量，边连接"最近的邻居"。搜索时从入口节点出发，沿边向目标方向移动。

3.2 Navigable（可导航）

"可导航"意味着搜索算法可以贪心地沿着图移动：

搜索步骤：
  1. 从入口节点开始
  2. 检查当前节点的所有邻居
  3. 如果某个邻居比当前节点更接近查询向量，就跳到那个邻居
  4. 重复 2-3，直到没有更近的邻居
  5. 当前节点就是搜索结果

flowchart LR
    Entry["🚪 入口节点"] --> N1["节点 A"]
    N1 --> N2["节点 B<br/>更接近查询!"]
    N2 --> N3["节点 C<br/>又更近!"]
    N3 --> Result["✅ 最近节点<br/>没有邻居更近了"]

    style Entry fill:#EFF6FF,stroke:#2563EB
    style Result fill:#ECFDF5,stroke:#059669,stroke-width:2px

3.3 Hierarchical（分层）

HNSW 的最大创新。单层图的搜索复杂度是 O(log N)，但当图很大时，搜索路径仍然较长。HNSW 通过分层来解决：

Layer 2:  ○────○        ← 稀疏层：节点少，边长（跨大步）
          │    │
Layer 1:  ○──○──○──○     ← 中间层：节点适中
          │  │  │  │
Layer 0:  ○─○─○─○─○─○   ← 密集层：包含所有节点，边短（精确）

搜索过程：

1. 从最高层（最稀疏）的入口点开始
2. 在当前层贪心搜索，找到最近节点
3. 下降到下一层，从步骤2的结果继续搜索
4. 重复直到第0层（最密集）
5. 在第0层找到最终结果

这就像从"全国地图"逐步缩放到"街道地图"：

• 高层：快速定位到目标城市（大步长，少节点）
• 低层：精确导航到目标地址（小步长，多节点）

四、HNSW 的三个关键参数

参数	含义	效果
M	每个节点最多有多少邻居	M↑ → 精度↑、索引大小↑、构建时间↑
efConstruction	构建索引时的搜索深度	↑ → 索引质量↑、构建时间↑
ef	查询时的搜索深度	↑ → 召回率↑、查询速度↓

本项目通过 langchain-milvus 创建 collection，当前显式使用M=16、efConstruction=200、ef=64。这些是本项目的当前配置，不是适用于所有数据规模的固定标准；如果要确认运行中 collection 的真实参数，应查看 collection 的 index 描述或实际创建日志。

五、HNSW vs 其他索引

索引类型	原理	优点	缺点
FLAT	暴力搜索	100% 精度	O(N×D) 时间
IVF_FLAT	K-means 聚类 + 只搜最近聚类	速度快	聚类边界可能漏掉
HNSW	分层可导航小世界图	速度快 + 精度高	内存占用较大
DiskANN	基于磁盘的图索引	内存占用小	需要 SSD

本项目选择 HNSW 的原因：当前知识库规模相对可控，同时更看重低延迟和高召回。Milvus 官方对 HNSW 的定位是低延迟、较高搜索准确性，但内存开销更高。项目文档中的规模分档只能作为选型起点，不能作为官方阈值；真实项目要用评测集和压测结果确认召回率、P95 延迟和内存占用。

六、在本项目中的体现

本项目的MilvusHybridStore通过 LangChain 封装创建 Milvus collection，dense 侧显式使用 HNSW，sparse 侧显式使用 BM25。对于当前项目规模，先使用明确参数可以降低歧义；当数据量、QPS、过滤条件或召回目标变化时，再通过 index 描述、压测和召回评测决定是否调参。

---