1.面试问题 #

在向量数据库中，HNSW、LSH和PQ是实现高效相似性搜索和数据管理的三种核心技术。请分别阐述它们的核心原理、主要作用、各自的优缺点以及典型的适用场景。

2.参考答案 #

在向量数据库中，HNSW (Hierarchical Navigable Small World)、LSH (Locality-Sensitive Hashing) 和 PQ (Product Quantization) 是三种关键的索引与压缩技术，它们共同服务于加速高维向量的相似性搜索和优化存储。

2.1 HNSW (Hierarchical Navigable Small World) #

2.1.1 核心原理 #

HNSW 是一种基于图结构的近似最近邻（ANN）搜索算法。它通过构建一个多层图结构来组织所有向量：

• 上层（稀疏层）：节点较少，连接稀疏，像"高速公路"，用于快速定位大致的搜索区域
• 下层（密集层）：节点较多，连接密集，像"小路"，用于在该区域内进行精细搜索

查询时，算法会从上层稀疏图开始，通过贪心策略快速跳转到与查询向量最相似的邻居，然后逐层向下深入到密集的底层图，最终快速找到近似最近邻点。

2.1.2 主要作用与优势 #

• 高精度快速搜索：在大规模向量数据中，HNSW 在查询速度和精度之间取得了优秀的平衡
• 时间复杂度优秀：搜索复杂度为 O(log N)，其中N是向量总数
• 支持动态更新：可以在运行时添加或删除向量，无需重建整个索引
• 内存效率相对较高：相比暴力搜索，内存使用更加合理

2.1.3 缺点 #

• 内存占用较高：由于需要维护复杂的多层图结构，HNSW 通常会占用较多的内存资源
• 构建时间较长：索引构建过程相对耗时，特别是对于超大规模数据集

2.1.4 适用场景 #

• 十亿级数据规模的实时相似性检索
• 推荐系统、图像检索、NLP等企业级应用
• 对搜索精度要求较高的场景

2.2 LSH (Locality-Sensitive Hashing) #

2.2.1 核心原理 #

LSH 是一种基于哈希的近似最近邻搜索技术。它设计了一组特殊的哈希函数，能够将相似的向量以较高的概率映射到同一个或相邻的哈希桶中，而不相似的向量则尽量分散到不同的哈希桶。

核心思想：

• 设计哈希函数族，使得相似向量有更高概率产生相同的哈希值
• 通过多个哈希表提高召回率
• 在哈希桶内进行精确搜索

2.2.2 主要作用与优势 #

• 极速粗筛：通过哈希桶快速缩小搜索范围，查询时只需检查查询向量所在桶及相邻桶内的候选项，而非全部数据，从而实现极快的检索速度（接近 O(1)）
• 去重与过滤：在图像去重等场景中，相似图片的向量会被"扔"到同一个桶中，方便直接在桶内查找重复项
• 可扩展性强：支持分布式部署，适合超大规模数据
• 理论保证：有严格的理论基础，可以控制假阳性和假阴性率

2.2.3 缺点 #

• 精度损失：LSH 的核心是概率性映射，因此在追求极致速度的同时，可能会牺牲一定的搜索精度
• 参数调优复杂：需要根据数据特征调整哈希函数数量和参数
• 内存开销：需要维护多个哈希表

2.2.4 适用场景 #

• 需要极速粗筛的场景
• 去重、过滤重复内容
• 处理文本、图像特征向量等高维数据
• 推荐系统、图像检索等海量数据近似查询

2.3 PQ (Product Quantization) #

2.3.1 核心原理 #

PQ 是一种向量压缩技术，旨在大幅减少向量数据的存储空间并加速距离计算。其核心思想是：

1. 向量切分：将高维向量（如1024维）拆分成多个低维子向量（如16个64维）
2. 子向量聚类：对每个子向量集合进行聚类，生成聚类中心（或称"码字"）
3. 编码存储：存储时，不再保存原始的子向量，而是用其所属聚类中心的编号（码字索引）来表示

例如，一个1024维向量拆成16块后，每块用8位编号表示，大大减少存储空间。

2.3.2 主要作用与优势 #

• 压缩存储：显著降低向量数据的内存和磁盘占用，通常可以压缩到原来的1/10到1/100
• 加速计算：在计算向量间距离时，只需计算对应聚类中心编号之间的距离，而非原始高维向量的距离，从而大幅加速距离计算
• 保持精度：通过合理的子向量分割和聚类，可以在压缩的同时保持较高的搜索精度
• 易于实现：算法相对简单，易于工程实现

2.3.3 缺点 #

• 轻微精度损失：由于用码字近似表示原始向量，会引入一定的量化误差，导致搜索精度略有下降
• 训练开销：需要预先训练码本，对于动态数据可能不够灵活
• 参数敏感：子向量分割数量和聚类中心数量需要仔细调优

2.3.4 适用场景 #

• 移动端、内存受限场景
• 存储成本敏感的应用
• 工业级向量检索系统
• 需要平衡存储成本和搜索精度的场景

2.4 三种技术的对比分析 #

2.5 技术组合使用策略 #

在实际应用中，这三种技术常常结合使用以达到最佳的性能和资源利用效率：

2.5.1 PQ + HNSW 组合 #

• PQ压缩：先用PQ压缩向量，减少内存占用
• HNSW索引：在压缩后的向量上构建HNSW索引
• 优势：既节省内存又保持高搜索精度
• 应用：Milvus等主流向量数据库的典型组合

2.5.2 LSH + 精确搜索组合 #

• LSH粗筛：用LSH快速筛选候选集
• 精确搜索：在候选集内进行精确的相似度计算
• 优势：在保证精度的同时大幅提升搜索速度
• 应用：大规模推荐系统的两阶段检索

2.5.3 多级索引策略 #

• 第一级：LSH进行快速粗筛
• 第二级：PQ压缩的向量进行快速距离计算
• 第三级：HNSW进行精确的最近邻搜索
• 优势：兼顾速度、精度和存储效率

2.6 技术选型建议 #

2.6.1 根据数据规模选择 #

• 小规模（<100万）：直接使用HNSW
• 中规模（100万-1亿）：PQ + HNSW组合
• 大规模（>1亿）：LSH + PQ + HNSW多级索引

2.6.2 根据精度要求选择 #

• 高精度要求：优先选择HNSW
• 速度优先：选择LSH进行粗筛
• 存储受限：必须使用PQ压缩

2.6.3 根据应用场景选择 #

• 实时推荐：LSH + 精确搜索
• 图像检索：PQ + HNSW
• 文本搜索：HNSW（对精度要求高）
• 去重应用：LSH（速度优先）

2.7 技术架构图 #

2.8 总结 #

HNSW、LSH和PQ是向量数据库中的三大核心技术，各有特色：

• HNSW：追求高精度和快速搜索，适合对精度要求高的场景
• LSH：追求极致速度，适合需要快速粗筛和去重的场景
• PQ：追求存储效率，适合内存受限和存储成本敏感的场景

在实际应用中，这三种技术往往不是单独使用，而是根据具体需求进行组合，形成多级索引策略，以达到速度、精度和存储效率的最佳平衡。选择合适的组合策略是构建高效向量数据库的关键。