第 114 题：HNSW的图索引构建，邻居选择策略与连通性保证？
题目
HNSW的图索引构建，邻居选择策略与连通性保证？
完整讲解
一、HNSW 的图结构
HNSW（Hierarchical Navigable Small World）是多层图索引：底层（层 0）包含所有节点，上层是下层的稀疏子集，形成「塔」结构。每节点以概率 $p$（如 $1/M$）进入上一层，形成多层级。查询时从顶层入口出发，在当前层贪心走到局部最近邻，再下到底层继续贪心，得到近似最近邻。复杂度约 $O(\log N)$ 层数 × 每层步数。
二、图索引构建（插入）
- 新节点插入：随机得到其最高层 $l$（如几何分布）；从顶层入口开始，在每层用贪心（当前层找最近邻、沿边走到更近）找到该层的「插入邻居」候选，再按邻居选择策略确定最终连边并插入，然后进入下一层重复，直到层 0。
- 边数限制：每节点每层最多保留 $M$ 条出边（如 $M=16$），以控制图密度与查询时每步的候选数。插入时候选邻居数往往大于 $M$，需选 $M$ 条，即邻居选择策略。
三、邻居选择策略
- 简单策略：在候选集中选距离当前节点最近的 $M$ 个。可能使图过于「局部团」、长程连接少，连通性与导航性差。
- HNSW 的启发式：在候选里选 $M$ 个时，不仅看距离，还鼓励多样性（如选中的点彼此不要太近），使边更分散、图更「小世界」。具体可用贪心：依次选能最大程度增加当前邻居集覆盖的节点（如最小化与已选点的最小距离、或最大化到已选集的最小距离），在距离与多样性间折中。
- 连通性保证：若严格只选最近 $M$ 个，孤岛或弱连通可能出现。实践中通过（1）入口多、层间连接；（2）邻居选择时加入多样性/启发式；（3）构建时保证层 0 全连接或做连通分量检查，减少断连。HNSW 论文中的「neighbor selection」算法即为此设计，兼顾距离与图性质。
四、参数与工程
- $M$：每节点每层最大邻居数，大则图密、召回高、内存与计算增。
- $efConstruction$：构建时每层搜索的候选池大小，大则插入更准、图质量高、构建慢。
- 查询时 $efSearch$：底层搜索的候选池大小，大则召回高、延迟大。
面试要点
- 能说明 HNSW 的多层图、插入流程与每层边数限制 $M$。
- 能说清邻居选择不仅「最近 $M$」、要兼顾多样性/小世界，以及连通性风险的应对。
- 能列举 $M$、$efConstruction$、$efSearch$ 对构建质量、召回与延迟的影响。
记忆要点
- HNSW：多层图、插入时每层选 $M$ 个邻居；邻居选择要多样性、保证小世界与连通性。
- 仅最近 $M$ 易局部团、弱连通；启发式选多样邻居、多入口、层 0 检查可缓解。
- 参数：$M$（每层边数）、$efConstruction$（构建候选池）、$efSearch$（查询候选池）。