HNSW索引

HNSW（可导航小世界层次图）是一种近似最近邻搜索算法。它是一种常用的索引类型，可以提升高维向量（如表示嵌入的向量）查询性能。

使用方法

创建HNSW索引的方式取决于您使用的距离运算符。pgvector包含3种距离运算符：

使用以下SQL命令为查询中使用的运算符创建HNSW索引。

欧几里得L2距离 (vector_l2_ops)#

1
create index on items using hnsw (column_name vector_l2_ops);

内积 (vector_ip_ops)#

1
create index on items using hnsw (column_name vector_ip_ops);

余弦距离 (vector_cosine_ops)#

1
create index on items using hnsw (column_name vector_cosine_ops);

目前最多可为2000维的向量创建索引。

HNSW工作原理#

HNSW使用邻近图（根据节点间距离连接的图）来近似最近邻搜索。理解HNSW可以分为两部分：

• 层次结构(H): 算法在多个层级上运行
• 可导航小世界(NSW): 每个向量都是图中的一个节点，并与多个其他节点相连

层次结构

HNSW的层次结构特性建立在跳表(skip list)的概念之上。

跳表是一种多层链表结构。最底层是一个普通的链表，连接着有序的元素序列。上方的每一层都会基于固定概率从下层移除部分元素，形成一个更稀疏的子序列，从而"跳过"某些元素。

当搜索元素时，算法从顶层开始水平遍历链表。如果找到目标元素，算法停止并返回结果。否则，如果链表中的下一个元素大于目标值(或为NULL)，算法就会下降到下一层。由于每一层都比上层更密集(最底层连接所有元素)，最终一定能找到目标元素。跳表在搜索和插入/删除操作上都提供了O(log n)的平均时间复杂度。

可导航小世界网络

可导航小世界网络（Navigable Small World，NSW）是一种特殊的邻近图，它在节点之间包含了长距离连接。这些长距离连接支持图的"小世界"特性，意味着几乎每个节点都可以通过少量跳转到达其他任意节点。如果没有这些额外的长距离连接，到达远距离节点将需要多次跳转。

NSW中的"可导航"特性特指能够在图上对数级扩展贪婪搜索算法的能力，该算法尝试在每次跳转时仅做出局部最优选择。没有这个特性，图可能仍被视为具有远距离节点间短路径的小世界网络，但贪婪算法往往会错过这些路径。贪婪搜索非常适合NSW，因为它能快速导航且计算成本低。

**分层+**可导航小世界网络

HNSW结合了这两个概念。从分层角度来看，底层由节点间短连接组成的NSW构成。每一上层都会"跳过"元素，并在相距较远的节点间创建更长的连接。

与跳表类似，搜索从顶层开始，逐层向下直到找到目标元素。然而，与跳表在每层比较标量值来决定是否下降到下一层不同，HNSW使用的是多维距离度量（如欧几里得距离）。

何时应该创建 HNSW 索引？#

HNSW 应该是创建向量索引时的默认选择。当您不需要 100% 的精确度，并且愿意牺牲少量精确度来换取更高的吞吐量时，就可以添加这种索引。

与 IVFFlat 索引不同，您可以在表创建后立即安全地构建 HNSW 索引。HNSW 索引基于图结构，本质上不受 IVFFlat 相同限制的影响。随着新数据添加到表中，索引会自动填充，且索引结构将保持最优状态。

相关资源

在 pgvector 的 GitHub 页面 上阅读更多关于索引的内容。