HNSW：图索引如何击败树索引
内容提要
HNSW是主流向量数据库默认的近似最近邻索引算法，通过分层图结构实现高效搜索。文章从NSW图出发，详细推导HNSW设计，给出C语言实现，讨论参数调优、距离计算优化，并对比Vamana等竞品。HNSW在精度、速度、内存间取得平衡，搜索复杂度为O(log N)，但内存消耗大，动态更新和过滤搜索仍是挑战。
延伸解读
为何树索引在高维失效
文章指出，KD-tree、Ball-tree 等树索引在维度超过 20 后性能急剧下降，退化为暴力扫描。这是因为树索引依赖轴对齐的空间划分，而高维空间中数据分布稀疏且各维度关联复杂，导致划分效率极低。理解这一点有助于解释为何图索引成为高维向量检索的主流选择。
HNSW 的工程权衡
HNSW 在精度、速度和内存之间取得平衡，但并非万能。文章强调其内存消耗大，动态更新和过滤搜索仍是挑战。实际应用中需根据数据规模和硬件条件权衡：若内存充足且要求亚毫秒延迟，HNSW 是优选；若数据量达十亿级且内存受限，可考虑 DiskANN 等磁盘友好方案。
参数调优的实践要点
文章详细讨论了 M、efConstruction、ef 等参数的影响。M 控制图密度，影响内存和搜索质量；efConstruction 影响构建质量但不影响查询速度；ef 是查询时调整精度-速度权衡的关键。建议构建时用较大 efConstruction，查询时根据 SLA 调整 ef，并参考 Recall-QPS 曲线进行选型。
Q&A
HNSW索引相比树索引和哈希索引有什么优势？
HNSW通过分层图结构和贪心搜索，在高维向量检索中实现了精度、速度和内存之间的平衡。树索引在高维（超过20维）时退化为暴力扫描，哈希索引召回率不稳定，而HNSW在ANN-Benchmarks上长期霸榜，搜索复杂度为O(log N)。
HNSW的分层结构是如何工作的？
HNSW借鉴跳表思想，构建多层图：Layer 0包含所有节点，高层节点稀疏，边作为长程连接。搜索从最高层开始，贪心下降，每层只保留一个最近邻，最后在Layer 0进行beam search。这种设计将粗定位和精细定位分离，使搜索复杂度从NSW的多项式级降为O(log N)。
HNSW的插入算法主要步骤是什么？
插入新向量时，先随机分配层级l，然后从最高层贪心下降到l+1层，每层只保留一个最近邻作为入口点；接着从第l层到第0层，每层用efConstruction搜索候选，选择M个邻居建立双向边，并收缩超出的邻居；最后若新节点层级高于当前最高层，则更新入口点。
HNSW中参数M和efConstruction如何影响性能？
M控制图的密度，M越大内存占用越高、构建越慢，但搜索精度越高；M过小会导致图不连通。efConstruction控制构建时搜索宽度，越大邻居质量越高，但构建越慢，且不影响查询速度。一般建议M取16-32，efConstruction设为M的10-20倍。
HNSW搜索时ef参数的作用是什么？
ef是查询时的搜索宽度，控制精度-速度权衡。ef越大，候选越多，召回率越高，但QPS下降。例如在SIFT-1M上，ef=100时Recall@10约0.99，ef=200时约0.997。生产环境通常根据SLA设定，如要求99%召回率，ef约100。
HNSW的主要缺点有哪些？
HNSW的主要缺点包括：内存消耗大，十亿级数据需要数百GB内存；动态更新支持不佳，删除节点会破坏连通性，工业界常用segment重建；带过滤的搜索效率低，图遍历会浪费在不满足条件的节点上；构建成本高，十亿级数据构建需数小时。
HNSW与Vamana（DiskANN）的主要区别是什么？
HNSW是多层无向图，面向内存场景，长程连接由高层提供；Vamana是单层有向图，面向磁盘场景，通过RobustPrune算法和alpha参数显式保留长程边，并将节点数据连续存储以优化SSD读取。DiskANN在十亿级数据上以较低内存成本实现高召回，但延迟稍高。
HNSW在工业界有哪些典型应用？
HNSW被广泛用于向量数据库和搜索引擎，如Faiss、Milvus、Weaviate、Pinecone、Qdrant、Elasticsearch和pgvector。它常用于RAG（检索增强生成）、推荐系统、图像检索等场景，在毫秒级完成向量检索。
