分层可导航小世界 (HNSW) 图索引是一种数据结构，旨在在高维向量空间中高效执行近似最近邻 (ANN) 搜索。它将向量组织成多层图，其中每一层代表数据的简化版本，较高的层包含较少的节点和更稀疏的连接。其核心思想是通过从顶部（最粗略）层开始搜索，并在搜索向下移动到较低、更密集的层时逐步细化结果，从而实现快速遍历。与平面图结构相比，这种分层方法减少了所需的比较次数，从而平衡了速度和准确性。
HNSW 建立在“小世界”属性之上，其中大多数节点可以通过少数几个步骤从任何其他节点到达。层次结构中的每一层都是一个图，其中节点代表向量，边连接相似的向量。较高的层具有较少的节点和更长程的连接，允许算法快速跳过向量空间的大片区域。例如，在包含 100 万个图像嵌入的数据集中，顶层可能只包含 1,000 个节点，而底层包含所有向量。当插入一个新向量时，它会被随机分配到一个层（对于较高的层，概率会降低），并连接到该层及其以下所有层中的最近邻。这种概率分层确保了高效的缩放，并避免了上层因节点过多而过载。
在搜索过程中，HNSW 从顶层开始，识别出最近的入口点，并使用它们“向下导航”。在每一层，算法都会探索相邻节点以细化候选集，逐步将焦点缩小到最有希望的区域。例如，当搜索相似的文本嵌入时，顶层可能会快速过滤掉不相关的集群（例如，将医疗文档与电影评论分开），而较低的层会比较更精细的细节。使用束搜索（维护一个动态的顶部候选列表）确保搜索探索足够的可能性，而无需详尽的检查。通过利用层次结构和受控连接，HNSW 实现了亚线性搜索时间（例如，O(log N) 复杂度），同时保持了高召回率，使其适用于推荐系统或语义搜索引擎等实际应用。