Vector Database Basics: HNSW 详解
在机器学习和人工智能系统中，向量数据库是存储和搜索海量数据的关键工具。想象向量如同地图上的点，每个点都有其独特位置，这些“位置”帮助我们快速准确地找到所需信息。本文将深入解析 HNSW 索引，探讨其优势、工作原理及应用方法。
HNSW 索引与 Pgvector
Pgvector 是 PostgreSQL 的一个扩展，支持在数据库中存储和检索向量数据，其中就包括 HNSW（分层可导航小世界）索引。HNSW 索引源于 Malkov 和 Yashunin 的基础研究，为高维向量数据的近似最近邻搜索（ANN）提供了一种新颖的基于图的框架。
在高维数据场景中，传统索引因维度增加导致复杂度呈指数级增长，难以维持效率，而 HNSW 索引很好地解决了这一问题，能在不扫描整个数据集的情况下高效找到相似向量，这在处理大量高维向量数据时尤为重要。
近似最近邻搜索（ANN）
近似最近邻搜索（ANN）专注于在数据集中找到与给定查询点最接近的数据点。与精确最近邻搜索不同，ANN 在搜索准确性和计算效率之间进行权衡，因为在高维空间中，精确匹配的计算时间和资源成本可能过高。
ANN 主要分为三类，基于不同的数据结构：
- 树结构：通过层次化组织数据，在每个节点进行二元决策，逐步靠近查询点。
- 哈希结构：将数据点转换为低维空间中的代码，把相似项分组到相同桶中，以加快检索速度。
- 图结构：HNSW 所采用的结构，创建点的网络，其中边根据相似性度量连接邻居。
HNSW 凭借其多层图结构，有效应对“维度灾难”，在高维空间中实现高效的近似搜索，在保证搜索速度的同时，不过分追求完美匹配，而是注重实用性和性能。
HNSW 与 IVF 的区别
HNSW 与倒排文件（IVF）索引方法相比，突出优势在于对动态数据集的适应性。它能高效处理插入和删除操作，无需完全重建索引，这对数据不断变化的应用至关重要。
而 IVF 索引在添加新数据或删除旧数据时，往往需要完全重建，这既耗时又会影响实时搜索能力。HNSW 的设计避免了这一局限，为数据频繁变化的数据库提供了更可持续的解决方案。
HNSW 的工作原理
核心原则
HNSW 利用图结构组织数据，反映数据点之间的内在相似性，形成可导航的小世界网络。其核心原则是最小化图中任意两点之间的路径长度，确保每个点都能通过少量跳数到达其他点。这通过将数据组织到多个层来实现，每一层都提供更精细的数据视图。
受跳表启发
跳表是一种用于存储排序项目列表的数据结构，具有高效的搜索、插入和删除操作，HNSW 的层次设计受其启发。在跳表中，元素被组织到多个层，较高层提供快速遍历列表的捷径。
类似地，HNSW 构建多层图，顶层包含较少的节点，作为搜索查询的“高速公路”，引导搜索更接近目标，然后进入更密集的低层进行精细搜索。
“长”边的引入
在 HNSW 中，“长”边指的是图上层中跨越数据空间较大距离的连接，绕过许多中间节点。这些边对于实现小世界特性至关重要，能实现图中的快速跳转。
当搜索查询从顶层向下移动到底层时，边的长度减小，搜索区域变得越来越局部化，从而能以最小的计算开销精确识别最近邻。
解决传统图索引挑战
传统图索引技术在高维空间中常受“维度灾难”困扰，数据点之间的距离变得不那么有意义，难以高效组织和搜索数据，且在可扩展性和索引更新方面存在困难。
HNSW 通过其多层层次结构解决了这些问题。它通过在每一层降低维度来提高高维空间中的搜索效率，并能动态调整图结构，无需完全重建，特别适合数据点频繁变化的动态数据集。
如何创建 HNSW？
构建层次结构
HNSW 的层次结构本质上是一组分层图，每层以不同的抽象程度表示数据集。顶层节点最少，作为搜索查询的入口点，便于在数据空间中快速遍历。每一层依次增加密度，增加更多细节，直到到达包含所有数据点的基层。
- 初始化：从空结构开始。图最初没有节点，插入的第一个节点成为顶层的唯一成员。
- 层分配：对于每个新数据点，确定其在层次结构中的最大层 l。通常使用概率方法，如抛硬币或从几何分布中抽取，确保随着层高度的增加，节点的预期数量减少。
- 连接节点：将新节点插入到其分配的最大层及以下的每一层。在每一层中，将节点与其最近的邻居连接。节点在每一层拥有的连接（或边）数量可以是固定的或可变的，受图形所需稀疏度或密度等参数影响。
图的构建
图的构建是向层次结构中填充数据点，并基于相似性或接近度建立连接的过程。
- 寻找邻居：在当前层中识别插入的新节点的最近邻。这可能涉及搜索整个图或使用启发式方法限制搜索空间。最初，搜索从随机选择的节点或随着图的增长而更新的指定入口点开始。
- 更新连接：一旦确定了层中的最近邻，就建立新节点的连接。这可能需要更新邻居的连接，以确保图保持可导航性并保留小世界特性。
- 层下降：对节点最大层以下的每一层重复此过程，随着图变得更密集，细化对最近邻的搜索。这种迭代方法确保每个节点都被最佳地放置在层次结构中，保持高效的可导航性。
实现要点
HNSW 的实际实现可能因具体用例和性能要求而异，但有一些常见注意事项：
- 语言和库选择：可在多种编程语言中实现。C++ 因其在高级可用性和对内存及性能的低级控制之间的平衡而常被选用。像 nmslib 或 faiss 这样的库提供了优化的距离计算和图操作例程。
- 内存管理：高效的内存使用至关重要，尤其是对于大型数据集。这包括选择合适的数据结构来存储节点和边，以及管理层次层。
- 并行化：为了加快构建和查询过程，HNSW 实现可以利用并行计算技术。这包括并行化最近邻搜索和节点插入，以及管理可能出现的并发问题。
在 HNSW 的实现中，关注这些方面的细节可以显著影响索引的性能和可扩展性，使其适用于高维空间中搜索和数据检索的广泛应用。
HNSW 方法的优缺点
优点
- 文档完善：HNSW 的一大优势是其强大的文档和丰富的研究支持其方法。这一坚实的基础帮助开发人员和研究人员理解、实施和优化该算法以用于各种应用。
- 向量数据库中的首选索引：HNSW 已成为众多向量数据库引擎的首选索引。它在高维向量空间搜索操作中的效率使其在人工智能、机器学习以及需要基于向量相似性快速检索信息的类似领域中备受青睐。
- 可配置以实现高召回率和速度：HNSW 具有出色的可配置性，允许在不显著影响搜索速度的情况下调整以实现高召回率（检索最相关结果的能力）。这种平衡在搜索结果准确性至关重要且需要快速获取结果的场景中特别有价值。
挑战
- 内存密集型：HNSW 的性能在很大程度上依赖于将索引完全存储在内存中。虽然这有利于速度，但这种架构选择使 HNSW 更适合具有大量 RAM 可用性的系统。随着数据集的增长，特别是当高维向量达到数千万时，内存需求可能成为限制因素。
- 随内存而非磁盘扩展：与其他有效利用磁盘空间的数据存储和索引方法不同，HNSW 的设计要求整个索引适合可用内存。这一特性在为大规模数据集或内存资源受限的环境扩展系统时可能带来挑战。
在 Pgvector 中创建 HNSW 索引
将 HNSW 集成到项目中以获得高效的向量搜索能力非常简单，特别是借助 Timescale Cloud 上的 AI 和向量工具及其在 SQL 和 Python 环境中的支持。
通过 Timescale Cloud，开发人员可以使用 pgvector、pgvectorscale 和 pgai 扩展——这些扩展将 PostgreSQL 转变为易于使用且高性能的向量数据库，加上完全托管的云数据库体验。
以下是在不同环境中利用 HNSW 的方法，无论是在云平台还是使用开源版本，都能让向量数据库更强大、搜索更高效。
在 SQL 中使用 pgvector 在 Timescale 上创建 HNSW 索引
TimescaleDB 是 PostgreSQL 的扩展，旨在处理时间序列数据、事件和分析，它还通过 pgvector 扩展了其功能以支持向量操作。为存储在 PostgreSQL 数据库中的向量数据实现 HNSW 索引可以显著提高搜索性能。
在 SQL 中为表的嵌入列创建 HNSW 索引的方法如下：
plain
此命令为
document_embedding 表的 embedding 列创建一个名为 document_embedding_idx 的 HNSW 索引，使用余弦相似性操作（vector_cosine_ops）。该索引利用 HNSW 算法的速度和准确性，促进高效的最近邻搜索。在 Python 中使用 Timescale 库利用 HNSW
对于在 Python 环境中工作的人来说，Timescale Python 库简化了将 HNSW 索引应用于向量数据的过程。
使用该库创建 HNSW 索引的方法如下：
plain
这行代码指示库在由
vec 对象管理的向量数据上创建 HNSW 索引。为了更好地控制索引过程，包括调整算法参数以获得更好的性能，可以指定其他选项，如下所示：
plain
这个扩展示例设置了
m、ef_construction 和 ef_search 参数来定制 HNSW 索引。其中，m 控制索引中每个元素的最大连接数，ef_construction 调整索引构建期间用于提高准确性的动态列表的大小，ef_search 影响搜索时间精度。克服 HNSW 的局限性
虽然 HNSW 是向量数据库中的首选索引，但对于处理大型数据集的开发人员来说，其内存密集型特性可能是一个障碍。而 pgvectorscale 在这方面表现出色，它在不占用过多磁盘空间和内存的情况下提供高性能。
通过向 pgvector 添加 StreamingDiskANN 索引，pgvectorscale 克服了像 HNSW 这样的内存中索引的局限性。它将部分索引存储在磁盘上，使得在向量工作负载增长时运行和扩展更具成本效益。由于 SSD 比 RAM 便宜得多，这大大降低了存储和搜索大量向量的成本。
Pgvectorscale 还支持流式过滤，即使在相似性搜索期间应用二次过滤，也能确保准确检索。它向 pgvector 添加了统计二进制量化（SBQ），比传统的量化方法提高了准确性。
结果是在索引占用更少磁盘和内存空间的情况下，以更高的准确性提高了搜索性能。而且，其成本仅为专用数据库（如 Pinecone）的四分之一。
pgai 将 AI 工作流引入 PostgreSQL，将其与 pgvectorscale 和 pgvector 相结合，使开发人员能够继续使用他们熟悉和喜爱的 PostgreSQL，将其转变为高性能的向量工作负载平台和 AI 应用程序构建平台。
结论
本文深入探讨了 HNSW 索引，它提高了高维数据空间中 ANNS 的效率和准确性。从其操作原理来看，HNSW 在性能和灵活性方面表现突出。
通过分解构建 HNSW 索引的过程并强调其优缺点，我们旨在全面了解其对向量数据库管理的影响。HNSW 索引兼具速度、精度和易用性，使其成为人工智能、机器学习等众多应用的首选索引。
尽管 HNSW 存在内存密集型和大规模数据集扩展方面的挑战，但其在促进快速准确搜索方面的优势不可否认。对于准备将 HNSW 集成到项目中的人来说，无论是通过 SQL 命令还是基于 Python 的 Timescale 库，过程都简单而强大。只需一行代码，就能释放向量数据的潜力，增强应用程序的搜索能力。
如果要处理不断增长的数据集，可以安装 pgvectorscale PostgreSQL 扩展，开始构建更具可扩展性的 AI 应用程序，实现更高性能的嵌入搜索和经济高效的存储。