第2070篇：向量数据库内部原理——HNSW算法为什么这么快
大约 8 分钟
第2070篇：向量数据库内部原理——HNSW算法为什么这么快
适读人群：想深入理解向量检索原理的工程师 | 阅读时长：约19分钟 | 核心价值：理解HNSW的层级跳表结构和ANN近似最近邻搜索原理，指导索引参数调优
用了这么多向量数据库，大多数工程师只知道调参数，不知道参数背后的原理。
为什么HNSW的ef_construction越大，建索引越慢但搜索越准？M参数是什么意思？为什么HNSW用的内存比IVFFlat多很多？
这篇文章把HNSW的原理讲清楚，让你知其然也知其所以然。
向量检索的核心问题
首先明确问题：给定一个查询向量q，在数百万个向量中找到最相似的Top-K个。
暴力搜索：计算q和所有向量的余弦相似度，排序取Top-K。时间复杂度O(N)，N=100万向量，每次搜索需要约百毫秒。太慢。
需要近似最近邻（ANN）搜索：牺牲一点点准确率，换取搜索速度大幅提升。
/**
* 暴力搜索 vs HNSW性能对比（概念演示）
*/
public class SearchPerformanceDemo {
/**
* 暴力搜索：精确但慢
*/
public List<SearchResult> bruteForceSearch(
float[] query, float[][] database, int topK) {
// 计算所有距离，O(N * D)
PriorityQueue<SearchResult> pq = new PriorityQueue<>(
Comparator.comparingDouble(SearchResult::score));
for (int i = 0; i < database.length; i++) {
double score = cosineSimilarity(query, database[i]);
pq.offer(new SearchResult(i, score));
}
return pq.stream()
.sorted(Comparator.comparingDouble(SearchResult::score).reversed())
.limit(topK)
.toList();
}
// HNSW搜索的时间复杂度是 O(log N)，比暴力快1000倍
// 代价：有1-5%的召回率损失
record SearchResult(int id, double score) {}
}HNSW算法原理
HNSW = Hierarchical Navigable Small World（层级可导航小世界图）
核心思想：建立多层图结构，高层稀疏（用于快速定位区域），低层稠密（用于精确搜索）。
/**
* HNSW核心数据结构的Java实现（简化版，用于理解原理）
*
* 真实的HNSW会用C++实现，这里只是帮助理解概念
*/
public class HnswIndexConcept {
// 每个向量节点在各层的连接
// neighbors[i][layer] = 节点i在layer层的邻居列表
private final Map<Integer, Map<Integer, List<Integer>>> neighbors = new HashMap<>();
// 所有向量
private final List<float[]> vectors = new ArrayList<>();
// HNSW参数
private final int M; // 每个节点的最大连接数（每层）
private final int maxM0; // 第0层的最大连接数（通常是M的2倍）
private final int efConstruction; // 构建时的搜索宽度
private final double mL; // 层级概率因子
public HnswIndexConcept(int M, int efConstruction) {
this.M = M;
this.maxM0 = M * 2;
this.efConstruction = efConstruction;
this.mL = 1.0 / Math.log(M); // 决定节点插入到哪一层的概率
}
/**
* 插入新向量
* 这是HNSW的核心操作
*/
public void insert(float[] vector) {
int newId = vectors.size();
vectors.add(vector);
// 1. 随机决定这个节点插入到哪一层
// 层越高，概率越小（指数衰减）
int insertLayer = randomLayer();
Map<Integer, List<Integer>> nodeNeighbors = new HashMap<>();
neighbors.put(newId, nodeNeighbors);
if (vectors.size() == 1) {
// 第一个节点，直接成为各层的入口点
return;
}
// 2. 从最高层开始，贪心搜索直到insertLayer
int entryPoint = getEntryPoint();
for (int layer = getMaxLayer(); layer > insertLayer; layer--) {
// 在高层，只做贪心搜索，不建连接
List<Integer> neighbors = greedySearch(vector, entryPoint, 1, layer);
entryPoint = neighbors.get(0);
}
// 3. 在insertLayer及以下，建立双向连接
for (int layer = Math.min(insertLayer, getMaxLayer()); layer >= 0; layer--) {
int maxNeighbors = layer == 0 ? maxM0 : M;
// 找候选邻居（efConstruction个）
List<Integer> candidates = searchLayer(vector, entryPoint, efConstruction, layer);
// 选择最近的maxNeighbors个作为实际邻居
List<Integer> selectedNeighbors = selectNeighbors(vector, candidates, maxNeighbors);
// 建立连接
nodeNeighbors.put(layer, new ArrayList<>(selectedNeighbors));
// 双向连接：更新邻居的连接列表（重要！保证图的连通性）
for (int neighbor : selectedNeighbors) {
addNeighborConnection(neighbor, newId, layer, maxNeighbors);
}
entryPoint = candidates.get(0);
}
}
/**
* 搜索最近邻
*/
public List<Integer> search(float[] query, int topK, int efSearch) {
int entryPoint = getEntryPoint();
// 从最高层贪心搜索到第1层
for (int layer = getMaxLayer(); layer >= 1; layer--) {
List<Integer> result = greedySearch(query, entryPoint, 1, layer);
entryPoint = result.get(0);
}
// 在第0层进行更宽泛的搜索（efSearch控制搜索宽度）
List<Integer> candidates = searchLayer(query, entryPoint, efSearch, 0);
// 返回最近的topK个
return candidates.stream()
.sorted(Comparator.comparingDouble(id -> -cosineSimilarity(query, vectors.get(id))))
.limit(topK)
.toList();
}
private int randomLayer() {
// 层级概率分布：exp(-层数/mL)
return (int)(-Math.log(Math.random()) * mL);
}
private List<Integer> greedySearch(float[] query, int entryPoint, int topK, int layer) {
// 贪心搜索：每次移动到更近的邻居
Set<Integer> visited = new HashSet<>();
PriorityQueue<Integer> candidates = new PriorityQueue<>(
Comparator.comparingDouble(id -> -similarity(query, id)));
candidates.add(entryPoint);
visited.add(entryPoint);
while (!candidates.isEmpty()) {
int current = candidates.poll();
List<Integer> currentNeighbors = getNeighbors(current, layer);
for (int neighbor : currentNeighbors) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
candidates.add(neighbor);
}
}
}
return visited.stream()
.sorted(Comparator.comparingDouble(id -> -similarity(query, id)))
.limit(topK)
.collect(Collectors.toList());
}
private List<Integer> searchLayer(float[] query, int entryPoint, int ef, int layer) {
// 更全面的搜索：维护一个大小为ef的候选集
// 这是真正的ANN搜索逻辑
PriorityQueue<int[]> dynamicList = new PriorityQueue<>(
Comparator.comparingDouble(a -> a[1])); // 最近优先
PriorityQueue<int[]> candidates = new PriorityQueue<>(
Comparator.comparingDouble(a -> -a[1])); // 最远优先（用于裁剪）
Set<Integer> visited = new HashSet<>();
int initDist = (int)(similarity(query, entryPoint) * 1000);
dynamicList.add(new int[]{entryPoint, initDist});
candidates.add(new int[]{entryPoint, initDist});
visited.add(entryPoint);
while (!dynamicList.isEmpty()) {
int[] nearest = dynamicList.poll();
int worstDist = candidates.peek()[1];
if (-nearest[1] > worstDist) break; // 不可能有更好的了
List<Integer> neighborList = getNeighbors(nearest[0], layer);
for (int neighbor : neighborList) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
int dist = (int)(similarity(query, neighbor) * 1000);
if (dist > worstDist || candidates.size() < ef) {
dynamicList.add(new int[]{neighbor, dist});
candidates.add(new int[]{neighbor, dist});
if (candidates.size() > ef) candidates.poll();
}
}
}
}
return candidates.stream()
.map(arr -> arr[0])
.collect(Collectors.toList());
}
private double similarity(float[] query, int id) {
return cosineSimilarity(query, vectors.get(id));
}
private double cosineSimilarity(float[] a, float[] b) {
double dot = 0, normA = 0, normB = 0;
for (int i = 0; i < a.length; i++) {
dot += a[i] * b[i];
normA += a[i] * a[i];
normB += b[i] * b[i];
}
return dot / (Math.sqrt(normA) * Math.sqrt(normB));
}
// 简化实现的占位方法
private int getEntryPoint() { return 0; }
private int getMaxLayer() { return 3; }
private List<Integer> getNeighbors(int id, int layer) { return List.of(); }
private void addNeighborConnection(int id, int newId, int layer, int maxConn) {}
private List<Integer> selectNeighbors(float[] v, List<Integer> candidates, int max) {
return candidates.subList(0, Math.min(max, candidates.size()));
}
}参数调优指南
理解了原理，参数调优就清晰了：
/**
* HNSW参数调优的工程实践
*/
public class HnswTuningGuide {
/*
* 核心参数：
*
* M（每层最大连接数，默认16）
* ├── 增大M：
* │ ├── 每个节点连接更多邻居
* │ ├── 搜索路径更短，召回率更高
* │ ├── 内存占用增加（约O(M*N)）
* │ └── 构建时间增加
* └── 推荐值：
* ├── 高召回率要求（99%+）：M=48-64
* ├── 平衡场景（95%+）：M=16-32（默认）
* └── 内存敏感：M=4-8（召回率会下降）
*
* ef_construction（构建时搜索宽度，默认200）
* ├── 控制构建阶段的搜索精度
* ├── 越大图质量越好，构建越慢
* └── 推荐值：
* ├── ef_construction >= 2*M（最低要求）
* ├── 一般场景：ef_construction=200
* └── 高质量要求：ef_construction=400-800
*
* ef_search（搜索时宽度，运行时可调）
* ├── 不影响索引，只影响搜索质量和速度
* ├── 越大召回率越高，搜索越慢
* └── 实践：
* ├── 起点：ef_search = max(50, topK * 10)
* ├── 测量召回率，按需增大
* └── 典型值：50-500
*/
/**
* pgvector中的HNSW参数设置示例
*/
public static final String PG_VECTOR_HNSW_INDEX = """
-- 创建HNSW索引
CREATE INDEX ON embeddings
USING hnsw (embedding vector_cosine_ops)
WITH (
m = 16, -- 每层最大连接数
ef_construction = 200 -- 构建时搜索宽度
);
-- 设置查询时的ef_search
SET hnsw.ef_search = 100;
-- 查询
SELECT id, content, 1 - (embedding <=> $1) as similarity
FROM embeddings
ORDER BY embedding <=> $1
LIMIT 10;
""";
/**
* 内存估算
* HNSW的内存开销比IVFFlat大，但搜索更快
*/
public static long estimateHnswMemoryBytes(
int numVectors,
int dimensions,
int M) {
// 向量存储
long vectorMemory = (long) numVectors * dimensions * 4L; // float32
// 图结构存储（每个节点约存M个邻居ID，每个ID 4字节）
// 第0层：2M个连接；其他层：M个连接；平均约1.33*M个连接
long graphMemory = (long) numVectors * M * 4L * 4L; // 乘4是经验系数
return vectorMemory + graphMemory;
}
/**
* 召回率基准测试
* 通过对比精确搜索结果来测量ANN的召回率
*/
public double measureRecallAt(
float[][] testQueries,
int topK,
List<Integer>[] exactResults,
List<Integer>[] approximateResults) {
double totalRecall = 0;
for (int i = 0; i < testQueries.length; i++) {
Set<Integer> exact = new HashSet<>(exactResults[i]);
Set<Integer> approximate = new HashSet<>(approximateResults[i]);
// 交集大小 / exact结果大小
Set<Integer> intersection = new HashSet<>(exact);
intersection.retainAll(approximate);
totalRecall += (double) intersection.size() / topK;
}
return totalRecall / testQueries.length;
}
}IVFFlat vs HNSW对比
/**
* IVFFlat和HNSW的特性对比
* 帮助选择合适的索引类型
*/
public class IndexTypeComparison {
/*
* IVFFlat（倒排文件索引）：
* ─────────────────────
* 原理：将向量空间分成nlist个聚类（Voronoi格），
* 搜索时只在最近的nprobe个聚类里查找
*
* 优点：
* ├── 内存占用小（约向量大小 + 索引开销）
* ├── 构建快
* └── 内存占用可预测
*
* 缺点：
* ├── 召回率不如HNSW
* ├── nprobe需要调优（nprobe越大越准，但越慢）
* └── 不适合频繁插入（需要重建索引）
*
* 推荐场景：
* ├── 数据集 > 1亿（HNSW内存放不下）
* ├── 内存有限
* └── 批量更新场景
*
* HNSW（层级小世界图）：
* ─────────────────────
* 优点：
* ├── 召回率高（95-99%）
* ├── 搜索速度快（O(log N)）
* └── 支持实时插入（不需要重建）
*
* 缺点：
* ├── 内存占用大（约向量的2-3倍）
* └── 构建时间长
*
* 推荐场景：
* ├── 数据集 < 1亿
* ├── 要求高召回率（99%+）
* └── 实时插入场景
*/
// 典型配置参考
public static final String IVFFLAT_CONFIG = """
-- IVFFlat：适合大数据集，内存有限的场景
CREATE INDEX ON embeddings
USING ivfflat (embedding vector_cosine_ops)
WITH (lists = 100); -- lists约等于sqrt(N)
-- 查询时nprobe = lists的5-10%
SET ivfflat.probes = 10;
""";
public static final String HNSW_CONFIG = """
-- HNSW：适合中小数据集，要求高性能的场景
CREATE INDEX ON embeddings
USING hnsw (embedding vector_cosine_ops)
WITH (m = 16, ef_construction = 200);
-- 查询时ef_search，按需调整
SET hnsw.ef_search = 100;
""";
}实战调优案例
我在一个生产系统上的调优记录：
| 配置 | 构建时间 | 内存使用 | 搜索QPS | Recall@10 |
|---|---|---|---|---|
| HNSW M=8, ef=100 | 2.1h | 4.2GB | 1850 | 88.3% |
| HNSW M=16, ef=200 | 4.8h | 7.1GB | 1620 | 94.7% |
| HNSW M=32, ef=400 | 11h | 12.3GB | 1380 | 97.8% |
| IVFFlat lists=256 | 0.8h | 2.8GB | 980 | 91.2% |
数据集：200万条，768维向量。
结论：M=16, ef_construction=200是默认配置，通常是好的起点。如果Recall不够，先增大ef_search（不需要重建索引），再考虑增大M（需要重建）。