向量数据库：HNSW 算法详解

主流向量数据库

HNSW 算法详解

算法设计基础

跳表（Skip List）是一种概率性平衡数据结构，通过多层链表加速搜索。最底层（L0）包含所有元素，上层每层以概率递减的方式抽样节点。查询时从最高层开始，通过'向右比较→降层'的机制减少访问节点数。

可导航小世界（Navigable Small World, NSW）通过构建兼具局部紧密连接和全局长距离跳跃的图结构实现高效搜索。其特点在于：

• 短边保证局部搜索精度
• 长边实现跨区域快速导航

HNSW 核心架构

HNSW（Hierarchical Navigable Small World）融合跳表与 NSW 思想，构建多层图结构：

1. 分层设计：顶层包含最少节点，随层级下降节点密度增加
2. 动态插入：新节点随机分配最大层数，按指数衰减分布（类似跳表）
3. 搜索路径：从顶层开始逐层细化，每层采用贪婪算法寻找近邻