You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 

1 lines
36 KiB

<!doctypehtml><html lang=zh-CN><meta charset=UTF-8><meta content=width=device-width name=viewport><meta media="(prefers-color-scheme: light)" content=#222 name=theme-color><meta media="(prefers-color-scheme: dark)" content=#222 name=theme-color><meta content="Hexo 7.3.0" name=generator><link href=https://cdnjs.cloudflare.com rel=preconnect><link href=/images/apple-touch-icon-next.png rel=apple-touch-icon sizes=180x180><link href=/images/favicon-32x32-next.png rel=icon sizes=32x32 type=image/png><link href=/images/favicon-16x16-next.png rel=icon sizes=16x16 type=image/png><link color=#222 href=/images/logo.svg rel=mask-icon><meta content=2X6S9P7CAjXjVvw8YyQR8pCu-B0oEu7O9quLgxXuWyA name=google-site-verification><meta content=dV8JGNzi0c name=baidu-site-verification><script>!function(){var t=!1;function e(){var e;t||(t=!0,(e=document.createElement("script")).setAttribute("data-ad-client","ca-pub-7480618470784058"),e.async=!0,e.src="https://pagead2.googlesyndication.com/pagead/js/adsbygoogle.js",document.head.appendChild(e))}function a(){"requestIdleCallback"in window?window.requestIdleCallback(e,{timeout:5e3}):window.setTimeout(e,5e3)}"complete"===document.readyState?a():window.addEventListener("load",a,{once:!0})}()</script><link href=/css/main.css rel=stylesheet><link crossorigin=anonymous href=https://cdnjs.cloudflare.com/ajax/libs/font-awesome/7.0.0/css/all.min.css integrity=sha256-VHqXKFhhMxcpubYf9xiWdCiojEbY9NexQ4jh8AxbvcM= rel=stylesheet><link crossorigin=anonymous href=https://cdnjs.cloudflare.com/ajax/libs/fancyapps-ui/6.1.14/fancybox/fancybox.css integrity=sha256-mdaMxrItEW6hMIVJJNPKuX0B7KCSJQVEv3mVY4N2we4= rel=stylesheet><script class=next-config data-name=main type=application/json>{"hostname":"nicksxs.me","root":"/","images":"/images","scheme":"Pisces","darkmode":true,"version":"8.29.0","exturl":false,"sidebar":{"position":"left","width_expanded":320,"width_dual_column":240,"display":"post","padding":18,"offset":12},"hljswrap":true,"codeblock":{"theme":{"light":"default","dark":"stackoverflow-dark"},"prism":{"light":"prism","dark":"prism-dark"},"copy_button":{"enable":true,"style":"default"},"fold":{"enable":false,"height":500},"language":false},"bookmark":{"enable":false,"color":"#222","save":"auto"},"mediumzoom":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":true,"nav":null},"stickytabs":false,"motion":{"enable":false,"async":false,"duration":200,"transition":{"menu_item":"fadeInDown","post_block":"fadeIn","post_header":"fadeInDown","post_body":"fadeInDown","coll_header":"fadeInLeft","sidebar":"fadeInUp"}},"prism":false,"i18n":{"placeholder":"搜索...","empty":"没有找到任何搜索结果:${query}","hits_time":"找到 ${hits} 个搜索结果(用时 ${time} 毫秒)","hits":"找到 ${hits} 个搜索结果"},"algolia":{"appID":"663Q99OQQD","apiKey":"e461a1371d12cec1491c1153b288a9ed","indexName":"nicksxs","hits":{"per_page":10}}}</script><script defer src=/js/config.js></script><meta content="本文从跳表和小世界网络出发,拆解 HNSW 的分层图结构、索引构建与近似最近邻搜索流程,并说明 M、efConstruction、efSearch 等参数对召回率、性能和内存的影响。" name=description><meta content=article property=og:type><meta content="HNSW 算法原理详解:分层图构建、搜索流程与参数调优" property=og:title><meta content=https://nicksxs.me/2024/06/23/%E4%BB%8B%E7%BB%8D%E4%B8%80%E4%B8%8BHNSW%E7%AE%97%E6%B3%95/index.html property=og:url><meta content="Nicksxs's Blog" property=og:site_name><meta content="本文从跳表和小世界网络出发,拆解 HNSW 的分层图结构、索引构建与近似最近邻搜索流程,并说明 M、efConstruction、efSearch 等参数对召回率、性能和内存的影响。" property=og:description><meta content=zh_CN property=og:locale><meta content=https://img.nicksxs.me/blog/2c4njw.png property=og:image><meta content=https://img.nicksxs.me/blog/xg85mb.png property=og:image><meta content=https://img.nicksxs.me/blog/ytU7Ct.png property=og:image><meta content=https://img.nicksxs.me/blog/gVKHW0.png property=og:image><meta content=2024-06-23T14:50:50.000Z property=article:published_time><meta content=2024-06-23T14:50:50.000Z property=article:modified_time><meta content=Nicksxs property=article:author><meta content=LLM property=article:tag><meta content=算法 property=article:tag><meta content=summary name=twitter:card><meta content=https://img.nicksxs.me/blog/2c4njw.png name=twitter:image><link href=https://nicksxs.me/2024/06/23/%E4%BB%8B%E7%BB%8D%E4%B8%80%E4%B8%8BHNSW%E7%AE%97%E6%B3%95/ rel=canonical><script class=next-config data-name=page type=application/json>{"sidebar":"","isHome":false,"isPost":true,"lang":"zh-CN","comments":true,"permalink":"https://nicksxs.me/2024/06/23/%E4%BB%8B%E7%BB%8D%E4%B8%80%E4%B8%8BHNSW%E7%AE%97%E6%B3%95/","path":"2024/06/23/介绍一下HNSW算法/","title":"HNSW 算法原理详解:分层图构建、搜索流程与参数调优"}</script><script class=next-config data-name=calendar type=application/json>""</script><title>HNSW 算法原理详解:分层图构建、搜索流程与参数调优 | Nicksxs's Blog</title><script async src=https://www.googletagmanager.com/gtag/js?id=UA-61358619-1></script><script class=next-config data-name=google_analytics type=application/json>{"tracking_id":"UA-61358619-1","only_pageview":false,"measure_protocol_api_secret":null}</script><script defer src=/js/third-party/analytics/google-analytics.js></script><script defer src=/js/third-party/analytics/baidu-analytics.js></script><script async src=https://hm.baidu.com/hm.js?20f33b3c0c0eff9b1522999c0015646d></script><script crossorigin=anonymous defer integrity=sha256-QnJV4HT5r8i89ovZGRD86iynZqHerEbT2xt69vDM36I= src=https://cdnjs.cloudflare.com/ajax/libs/fancyapps-ui/6.1.14/fancybox/fancybox.umd.js></script><script defer src=/js/utils.js></script><script defer src=/js/sidebar.js></script><script defer src=/js/next-boot.js></script><script data-algolia-integrity=sha256-o49zoHLDPBm9WLg6AiliAVi3axCRTqe3ltTxLvhzAVg= data-algolia-src=https://cdnjs.cloudflare.com/ajax/libs/algoliasearch/5.36.0/lite/builds/browser.umd.js data-search-src=/js/third-party/search/algolia-search.js src=/js/third-party/search/algolia-search-loader.js></script><script defer src=/js/third-party/fancybox.js></script><noscript><link href=/css/noscript.css rel=stylesheet></noscript><link title="Nicksxs's Blog" href=/atom.xml rel=alternate type=application/atom+xml><body itemscope itemtype=http://schema.org/WebPage><div class=headband></div><main class=main><div class=column><header class=header itemscope itemtype=http://schema.org/WPHeader><div class=site-brand-container><div class=site-nav-toggle><div aria-label=切换导航栏 class=toggle role=button><span class=toggle-line></span><span class=toggle-line></span><span class=toggle-line></span></div></div><div class=site-meta><a class=brand href=/ rel=start><i class=logo-line></i><p class=site-title>Nicksxs's Blog</p><i class=logo-line></i></a><p class=site-subtitle itemprop=description>Java 运行时、生产诊断与 AI 工程实践</div><div class=site-nav-right><div class="toggle popup-trigger" aria-label=搜索 role=button><i class="fa fa-search fa-fw fa-lg"></i></div></div></div><nav class=site-nav><ul class="main-menu menu"><li class="menu-item menu-item-home"><a href=/ rel=section><i class="fa fa-home fa-fw"></i>首页</a><li class="menu-item menu-item-专题"><a href=/topics/ rel=section><i class="fa fa-layer-group fa-fw"></i>专题</a><li class="menu-item menu-item-工具"><a href=/tools/ rel=section><i class="fa fa-toolbox fa-fw"></i>工具</a><li class="menu-item menu-item-about"><a href=/about/ rel=section><i class="fa fa-user fa-fw"></i>关于我</a><li class="menu-item menu-item-tags"><a href=/tags/ rel=section><i class="fa fa-tags fa-fw"></i>标签</a><li class="menu-item menu-item-categories"><a href=/categories/ rel=section><i class="fa fa-th fa-fw"></i>分类</a><li class="menu-item menu-item-archives"><a href=/archives/ rel=section><i class="fa fa-archive fa-fw"></i>归档</a><li class="menu-item menu-item-search"><a class=popup-trigger role=button><i class="fa fa-search fa-fw"></i>搜索</a></ul></nav><div class=search-pop-overlay><div class="popup search-popup"><div class=search-header><span class=search-icon><i class="fa fa-search"></i></span><div class=search-input-container><input autocapitalize=off autocomplete=off class=search-input maxlength=80 placeholder=搜索... spellcheck=false type=search></div><span class=popup-btn-close role=button><i class="fa fa-times-circle"></i></span></div><div class=search-result-container><div class=search-result-icon><i class="fab fa-algolia fa-5x"></i></div></div></div></div></header><aside class=sidebar><div class="sidebar-inner sidebar-nav-active sidebar-toc-active"><ul class=sidebar-nav><li class=sidebar-nav-toc>文章目录<li class=sidebar-nav-overview>站点概览</ul><div class=sidebar-panel-container><div class="post-toc-wrap sidebar-panel"><div class="post-toc animated"><ol class=nav><li class="nav-item nav-level-2"><a class=nav-link href=#1-%E5%BC%95%E8%A8%80><span class=nav-number>1.</span> <span class=nav-text>1. 引言</span></a><li class="nav-item nav-level-2"><a class=nav-link href=#2-HNSW%E7%AE%97%E6%B3%95%E7%9A%84%E6%A0%B8%E5%BF%83%E6%80%9D%E6%83%B3><span class=nav-number>2.</span> <span class=nav-text>2. HNSW算法的核心思想</span></a><ol class=nav-child><li class="nav-item nav-level-3"><a class=nav-link href=#%E5%88%86%E5%B1%82%E7%BB%93%E6%9E%84><span class=nav-number>2.1.</span> <span class=nav-text>分层结构</span></a><li class="nav-item nav-level-3"><a class=nav-link href=#%E5%B0%8F%E4%B8%96%E7%95%8C%E5%9B%BE><span class=nav-number>2.2.</span> <span class=nav-text>小世界图</span></a><li class="nav-item nav-level-3"><a class=nav-link href=#%E8%BF%91%E4%BC%BC%E6%90%9C%E7%B4%A2><span class=nav-number>2.3.</span> <span class=nav-text>近似搜索</span></a></ol><li class="nav-item nav-level-2"><a class=nav-link href=#3-HNSW%E7%9A%84%E5%B7%A5%E4%BD%9C%E5%8E%9F%E7%90%86><span class=nav-number>3.</span> <span class=nav-text>3. HNSW的工作原理</span></a><ol class=nav-child><li class="nav-item nav-level-3"><a class=nav-link href=#%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E5%A4%9A%E5%B1%82%E5%9B%BE%E7%9A%84%E6%9E%84%E5%BB%BA%E8%BF%87%E7%A8%8B><span class=nav-number>3.1.</span> <span class=nav-text>数据结构:多层图的构建过程</span></a><li class="nav-item nav-level-3"><a class=nav-link href=#%E6%90%9C%E7%B4%A2%E8%BF%87%E7%A8%8B-%E8%87%AA%E9%A1%B6%E5%90%91%E4%B8%8B%E7%9A%84%E8%B4%AA%E5%A9%AA%E6%90%9C%E7%B4%A2><span class=nav-number>3.2.</span> <span class=nav-text>搜索过程:自顶向下的贪婪搜索</span></a><li class="nav-item nav-level-3"><a class=nav-link href=#%E6%8F%92%E5%85%A5%E6%96%B0%E5%90%91%E9%87%8F%E7%9A%84%E8%BF%87%E7%A8%8B><span class=nav-number>3.3.</span> <span class=nav-text>插入新向量的过程</span></a></ol><li class="nav-item nav-level-2"><a class=nav-link href=#4-HNSW%E7%9A%84%E6%80%A7%E8%83%BD%E5%88%86%E6%9E%90><span class=nav-number>4.</span> <span class=nav-text>4. HNSW的性能分析</span></a><ol class=nav-child><li class="nav-item nav-level-3"><a class=nav-link href=#%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%E5%88%86%E6%9E%90><span class=nav-number>4.1.</span> <span class=nav-text>时间复杂度分析</span></a><li class="nav-item nav-level-3"><a class=nav-link href=#%E7%A9%BA%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%E5%88%86%E6%9E%90><span class=nav-number>4.2.</span> <span class=nav-text>空间复杂度分析</span></a><li class="nav-item nav-level-3"><a class=nav-link href=#%E4%B8%8E%E5%85%B6%E4%BB%96ANN%E7%AE%97%E6%B3%95%E7%9A%84%E6%AF%94%E8%BE%83><span class=nav-number>4.3.</span> <span class=nav-text>与其他ANN算法的比较</span></a></ol><li class="nav-item nav-level-2"><a class=nav-link href=#5-HNSW%E7%9A%84%E5%AE%9E%E9%99%85%E5%BA%94%E7%94%A8><span class=nav-number>5.</span> <span class=nav-text>5. HNSW的实际应用</span></a><ol class=nav-child><li class="nav-item nav-level-3"><a class=nav-link href=#%E5%9C%A8%E6%8E%A8%E8%8D%90%E7%B3%BB%E7%BB%9F%E4%B8%AD%E7%9A%84%E5%BA%94%E7%94%A8><span class=nav-number>5.1.</span> <span class=nav-text>在推荐系统中的应用</span></a><li class="nav-item nav-level-3"><a class=nav-link href=#%E5%9C%A8%E5%9B%BE%E5%83%8F%E6%A3%80%E7%B4%A2%E4%B8%AD%E7%9A%84%E5%BA%94%E7%94%A8><span class=nav-number>5.2.</span> <span class=nav-text>在图像检索中的应用</span></a><li class="nav-item nav-level-3"><a class=nav-link href=#%E5%9C%A8%E8%87%AA%E7%84%B6%E8%AF%AD%E8%A8%80%E5%A4%84%E7%90%86%E4%B8%AD%E7%9A%84%E5%BA%94%E7%94%A8><span class=nav-number>5.3.</span> <span class=nav-text>在自然语言处理中的应用</span></a></ol><li class="nav-item nav-level-2"><a class=nav-link href=#6-HNSW%E7%9A%84%E4%BC%98%E5%8C%96%E5%92%8C%E5%8F%98%E7%A7%8D><span class=nav-number>6.</span> <span class=nav-text>6. HNSW的优化和变种</span></a><ol class=nav-child><li class="nav-item nav-level-3"><a class=nav-link href=#%E5%8F%82%E6%95%B0%E8%B0%83%E4%BC%98%E6%8A%80%E5%B7%A7><span class=nav-number>6.1.</span> <span class=nav-text>参数调优技巧</span></a><li class="nav-item nav-level-3"><a class=nav-link href=#%E5%B8%B8%E8%A7%81%E7%9A%84HNSW%E5%8F%98%E7%A7%8D%E7%AE%97%E6%B3%95%E4%BB%8B%E7%BB%8D><span class=nav-number>6.2.</span> <span class=nav-text>常见的HNSW变种算法介绍</span></a></ol><li class="nav-item nav-level-2"><a class=nav-link href=#7-%E5%AE%9E%E7%8E%B0HNSW%E7%9A%84%E6%8C%91%E6%88%98%E4%B8%8E%E8%A7%A3%E5%86%B3%E6%96%B9%E6%A1%88><span class=nav-number>7.</span> <span class=nav-text>7. 实现HNSW的挑战与解决方案</span></a><ol class=nav-child><li class="nav-item nav-level-3"><a class=nav-link href=#%E5%A4%A7%E8%A7%84%E6%A8%A1%E6%95%B0%E6%8D%AE%E9%9B%86%E7%9A%84%E5%A4%84%E7%90%86><span class=nav-number>7.1.</span> <span class=nav-text>大规模数据集的处理</span></a><li class="nav-item nav-level-3"><a class=nav-link href=#%E5%B9%B6%E8%A1%8C%E5%8C%96%E5%92%8C%E5%88%86%E5%B8%83%E5%BC%8F%E5%AE%9E%E7%8E%B0><span class=nav-number>7.2.</span> <span class=nav-text>并行化和分布式实现</span></a><li class="nav-item nav-level-3"><a class=nav-link href=#%E5%8A%A8%E6%80%81%E6%9B%B4%E6%96%B0%E5%92%8C%E5%88%A0%E9%99%A4%E6%93%8D%E4%BD%9C%E7%9A%84%E5%A4%84%E7%90%86><span class=nav-number>7.3.</span> <span class=nav-text>动态更新和删除操作的处理</span></a></ol><li class="nav-item nav-level-2"><a class=nav-link href=#8-%E6%80%BB%E7%BB%93%E4%B8%8E%E5%B1%95%E6%9C%9B><span class=nav-number>8.</span> <span class=nav-text>8. 总结与展望</span></a></ol></div></div><div class="site-overview-wrap sidebar-panel"><div class="site-author animated" itemprop=author itemscope itemtype=http://schema.org/Person><img alt=Nicksxs class=site-author-image itemprop=image src=/uploads/avatar.jpg><p class=site-author-name itemprop=name>Nicksxs<div class=site-description itemprop=description>Nicksxs 的技术博客,深入 Java 运行时与生产诊断、低成本大模型推理和 Agent 工程实践。</div></div><div class="site-state-wrap animated"><nav class=site-state><div class="site-state-item site-state-posts"><a href=/archives/><span class=site-state-item-count>394</span> <span class=site-state-item-name>日志</span></a></div><div class="site-state-item site-state-categories"><a href=/categories/><span class=site-state-item-count>181</span> <span class=site-state-item-name>分类</span></a></div><div class="site-state-item site-state-tags"><a href=/tags/><span class=site-state-item-count>347</span> <span class=site-state-item-name>标签</span></a></div></nav></div><div class="links-of-author animated"><span class=links-of-author-item><a rel="noopener me" title="GitHub → https://github.com/nicksxs" href=https://github.com/nicksxs target=_blank><i class="fab fa-github fa-fw"></i>GitHub</a> </span><span class=links-of-author-item><a rel="noopener me" title="E-Mail → mailto:nicksxs1202@gmail.com" href=mailto:nicksxs1202@gmail.com target=_blank><i class="fa fa-envelope fa-fw"></i>E-Mail</a></span></div><div class="cc-license animated" itemprop=license><a class=cc-opacity href=https://creativecommons.org/licenses/by-nc-sa/4.0/ rel=noopener target=_blank><img alt="Creative Commons" src=https://cdnjs.cloudflare.com/ajax/libs/creativecommons-vocabulary/2020.11.3/assets/license_badges/small/by_nc_sa.svg></a></div><div class="widget-wrap sidebar-tag-cloud"><div class=tag-cloud-tags><a class=tag-cloud-10 href=/tags/Java/ style=font-size:16px>Java</a><a class=tag-cloud-9 href=/tags/leetcode/ style=font-size:15.62px>leetcode</a><a class=tag-cloud-8 href=/tags/LLM/ style=font-size:15.23px>LLM</a><a class=tag-cloud-8 href=/tags/%E7%94%9F%E6%B4%BB/ style=font-size:14.85px>生活</a><a class=tag-cloud-7 href=/tags/%E9%A2%98%E8%A7%A3/ style=font-size:14.46px>题解</a><a class=tag-cloud-6 href=/tags/SpringBoot/ style=font-size:14.08px>SpringBoot</a><a class=tag-cloud-6 href=/tags/MySQL/ style=font-size:14.08px>MySQL</a><a class=tag-cloud-5 href=/tags/C/ style=font-size:13.69px>C++</a><a class=tag-cloud-5 href=/tags/Redis/ style=font-size:13.31px>Redis</a><a class=tag-cloud-4 href=/tags/Tomcat/ style=font-size:12.92px>Tomcat</a><a class=tag-cloud-4 href=/tags/Mybatis/ style=font-size:12.92px>Mybatis</a><a class=tag-cloud-3 href=/tags/%E5%B0%8F%E6%8A%80%E5%B7%A7/ style=font-size:12.54px>小技巧</a><a class=tag-cloud-2 href=/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/ style=font-size:12.15px>数据结构</a><a class=tag-cloud-2 href=/tags/%E6%BA%90%E7%A0%81/ style=font-size:12.15px>源码</a><a class=tag-cloud-2 href=/tags/MQ/ style=font-size:11.77px>MQ</a><a class=tag-cloud-2 href=/tags/%E6%B6%88%E6%81%AF%E9%98%9F%E5%88%97/ style=font-size:11.77px>消息队列</a><a class=tag-cloud-2 href=/tags/RocketMQ/ style=font-size:11.77px>RocketMQ</a><a class=tag-cloud-2 href=/tags/%E8%BF%90%E5%8A%A8/ style=font-size:11.77px>运动</a><a class=tag-cloud-1 href=/tags/php/ style=font-size:11.38px>php</a><a class=tag-cloud-0 href=/tags/Spring/ style=font-size:11px>Spring</a><a class=tag-cloud-0 href=/tags/linux/ style=font-size:11px>linux</a><a class=tag-cloud-0 href=/tags/Docker/ style=font-size:11px>Docker</a><a class=tag-cloud-0 href=/tags/%E5%87%8F%E8%82%A5/ style=font-size:11px>减肥</a><a class=tag-cloud-0 href=/tags/%E8%B7%91%E6%AD%A5/ style=font-size:11px>跑步</a></div></div><div class="affiliate-creative affiliate-creative--sidebar" data-affiliate-id=tencent-cloud-server><a rel="sponsored noopener" aria-label=腾讯云服务器优惠 href=https://cloud.tencent.com/act/cps/redirect?redirect=6544&cps_key=2e33a1eedb380997d03618b4a5ba6ca7&from=console target=_blank><img alt="腾讯云 AI 焕新云服务器优惠" decoding=async height=241 loading=lazy src=/uploads/affiliate/tencent-cloud-server.webp width=690> </a><span class=affiliate-disclosure>推广</span></div></div></div></div><div class="sidebar-inner sidebar-blogroll"><div class="links-of-blogroll animated"><div class=links-of-blogroll-title><i class="fa fa-globe fa-fw"></i> 链接</div><ul class=links-of-blogroll-list><li class=links-of-blogroll-item><a href=https://covermusic.cn/ rel=noopener target=_blank title=https://covermusic.cn>69伙伴</a></ul></div></div></aside></div><div class="main-inner post posts-expand"><div class=post-block><article class=post-content itemscope itemtype=http://schema.org/Article lang=zh-CN><link href=https://nicksxs.me/2024/06/23/%E4%BB%8B%E7%BB%8D%E4%B8%80%E4%B8%8BHNSW%E7%AE%97%E6%B3%95/ itemprop=mainEntityOfPage><span hidden itemprop=author itemscope itemtype=http://schema.org/Person><meta content=/uploads/avatar.jpg itemprop=image><meta content=Nicksxs itemprop=name></span><span hidden itemprop=publisher itemscope itemtype=http://schema.org/Organization><meta content="Nicksxs's Blog" itemprop=name><meta content="Nicksxs 的技术博客,深入 Java 运行时与生产诊断、低成本大模型推理和 Agent 工程实践。" itemprop=description></span><span hidden itemprop=post itemscope itemtype=http://schema.org/CreativeWork><meta content="HNSW 算法原理详解:分层图构建、搜索流程与参数调优 | Nicksxs's Blog" itemprop=name><meta content="本文从跳表和小世界网络出发,拆解 HNSW 的分层图结构、索引构建与近似最近邻搜索流程,并说明 M、efConstruction、efSearch 等参数对召回率、性能和内存的影响。" itemprop=description></span><header class=post-header><h1 itemprop="name headline" class=post-title>HNSW 算法原理详解:分层图构建、搜索流程与参数调优</h1><div class=post-meta-container><div class=post-meta><span class=post-meta-item><span class=post-meta-item-icon><i class="far fa-calendar"></i> </span><span class=post-meta-item-text>发表于</span> <time itemprop="dateCreated datePublished" title="创建时间:2024-06-23 22:50:50" datetime=2024-06-23T22:50:50+08:00>2024-06-23</time> </span><span class=post-meta-item><span class=post-meta-item-icon><i class="far fa-folder"></i> </span><span class=post-meta-item-text>分类于</span> <span itemprop=about itemscope itemtype=http://schema.org/Thing><a href=/categories/%E7%AE%97%E6%B3%95/ itemprop=url rel=index><span itemprop=name>算法</span></a> </span></span><span class="post-meta-item cloudflare-page-counter" data-title="HNSW 算法原理详解:分层图构建、搜索流程与参数调优" data-increment=true data-path=/2024/06/23/%E4%BB%8B%E7%BB%8D%E4%B8%80%E4%B8%8BHNSW%E7%AE%97%E6%B3%95/ title=阅读次数><span class=post-meta-item-icon><i class="far fa-eye"></i> </span><span class=post-meta-item-text>阅读次数:</span> <span class=cloudflare-page-counter-count></span></span></div><div class=post-description>本文从跳表和小世界网络出发,拆解 HNSW 的分层图结构、索引构建与近似最近邻搜索流程,并说明 M、efConstruction、efSearch 等参数对召回率、性能和内存的影响。</div></div></header><div class=post-body itemprop=articleBody><p>结合AI写的一篇HNSW的介绍文章,算是向量数据库中比较核心的算法<h2 id=1-引言><a title="1. 引言" class=headerlink href=#1-引言></a>1. 引言</h2><p>向量数据库在当今人工智能和机器学习领域扮演着越来越重要的角色。随着数据规模的不断扩大和应用场景的日益复杂,传统的数据库系统已经难以满足高维向量数据的快速检索需求。在这个背景下,近似最近邻(Approximate Nearest Neighbor, ANN)搜索问题成为了一个热点研究方向。<p>HNSW(Hierarchical Navigable Small World)算法是解决ANN问题的一种高效方法。它通过构建一个多层次的图结构,结合小世界网络的特性,实现了对高维向量数据的快速、精确检索。本文将深入浅出地介绍HNSW算法的核心思想、工作原理以及实际应用。<h2 id=2-HNSW算法的核心思想><a title="2. HNSW算法的核心思想" class=headerlink href=#2-HNSW算法的核心思想></a>2. HNSW算法的核心思想</h2><p>HNSW算法的核心思想可以概括为三个关键点:分层结构、小世界图和近似搜索。<h3 id=分层结构><a class=headerlink href=#分层结构 title=分层结构></a>分层结构</h3><p>HNSW采用了一种多层次的图结构。想象一下,如果我们要在一个大城市中找到一个特定的地址,我们通常会先看城市地图,然后逐步缩小范围到区、街道,最后定位到具体门牌号。HNSW的分层结构就类似于这种由粗到细的搜索过程。这个就是之前介绍跳表的目的,就是现在稀疏的结构里可以快速定位,然后再往下层进行搜索,提高了搜索效率<br><img loading=lazy src=https://img.nicksxs.me/blog/2c4njw.png><h3 id=小世界图><a class=headerlink href=#小世界图 title=小世界图></a>小世界图</h3><p>小世界网络是一种特殊的图结构,它具有较短的平均路径长度和较高的聚类系数。在HNSW中,每一层都是一个小世界图。这种结构使得在图中的任意两点之间都存在一条相对较短的路径,大大提高了搜索效率。<h3 id=近似搜索><a class=headerlink href=#近似搜索 title=近似搜索></a>近似搜索</h3><p>与传统的KNN(K-Nearest Neighbors)算法不同,HNSW通过牺牲一小部分精度来换取显著的速度提升。它不保证一定能找到真正的最近邻,但可以以极高的概率找到足够接近的点,而且搜索速度要快得多。<h2 id=3-HNSW的工作原理><a title="3. HNSW的工作原理" class=headerlink href=#3-HNSW的工作原理></a>3. HNSW的工作原理</h2><h3 id=数据结构-多层图的构建过程><a class=headerlink href=#数据结构-多层图的构建过程 title=数据结构:多层图的构建过程></a>数据结构:多层图的构建过程</h3><ol><li>HNSW从底层开始构建,每个数据点都会出现在底层。<li>对于每个新插入的点,算法会随机决定它是否应该出现在上一层。这个过程一直持续到某一层,该点不再被选中。<li>在每一层,新点会与该层的其他点建立连接,形成小世界图结构。</ol><h3 id=搜索过程-自顶向下的贪婪搜索><a class=headerlink href=#搜索过程-自顶向下的贪婪搜索 title=搜索过程:自顶向下的贪婪搜索></a>搜索过程:自顶向下的贪婪搜索</h3><ol><li>搜索从最顶层开始,选择一个随机起点。<li>在当前层进行贪婪搜索,不断移动到离目标更近的邻居。<li>当在当前层无法找到更近的点时,下降到下一层继续搜索。<li>重复这个过程直到达到底层,得到最终结果。<br><img loading=lazy src=https://img.nicksxs.me/blog/xg85mb.png></ol><h3 id=插入新向量的过程><a class=headerlink href=#插入新向量的过程 title=插入新向量的过程></a>插入新向量的过程</h3><ol><li>确定新向量应该出现在哪些层。<li>从顶层开始,在每一层执行类似于搜索的过程,找到适合连接的邻居点。<li>建立连接,同时可能需要删除一些现有连接以维持图的结构特性。<br><img loading=lazy src=https://img.nicksxs.me/blog/ytU7Ct.png><br>论文中的算法是这样的<br><img loading=lazy src=https://img.nicksxs.me/blog/gVKHW0.png></ol><ul><li><p>红色节点表示新插入的数据点。在这个例子中,新节点被插入到了层级0和层级1。<li><p>红色实线表示新建立的同层连接。新节点与其邻近节点建立了连接。<li><p>红色虚线表示新建立的跨层连接。新节点在不同层级之间建立了连接。<li><p>绿色虚线箭头表示插入过程的路径。这条路径展示了算法如何从顶层开始,逐层下降,最终确定新节点的插入位置。<li><p>其他颜色的节点和灰色的连接线表示原有的HNSW结构。<li><p>插入过程从顶层开始,沿着绿色虚线所示的路径向下搜索。<li><p>在每一层,算法都会寻找最近的邻居节点,并决定是否在该层插入新节点。<li><p>在本例中,新节点被插入到了层级0(基础层)和层级1。这是因为HNSW使用概率方法来决定节点应该出现在哪些层级。<li><p>插入后,新节点与其邻近节点建立连接(红色实线),以维持图的小世界特性。<li><p>同时,新节点也与其在不同层级的对应节点建立跨层连接(红色虚线),以确保层级之间的快速访问。</ul><h2 id=4-HNSW的性能分析><a title="4. HNSW的性能分析" class=headerlink href=#4-HNSW的性能分析></a>4. HNSW的性能分析</h2><h3 id=时间复杂度分析><a class=headerlink href=#时间复杂度分析 title=时间复杂度分析></a>时间复杂度分析</h3><ul><li>搜索时间复杂度: O(log N),其中N是数据点的总数。<li>插入时间复杂度: 平均情况下为O(log N)。</ul><h3 id=空间复杂度分析><a class=headerlink href=#空间复杂度分析 title=空间复杂度分析></a>空间复杂度分析</h3><ul><li>空间复杂度: O(N log N),因为上层节点数量呈指数衰减。</ul><h3 id=与其他ANN算法的比较><a class=headerlink href=#与其他ANN算法的比较 title=与其他ANN算法的比较></a>与其他ANN算法的比较</h3><p>相比LSH(Locality-Sensitive Hashing)和Annoy等算法,HNSW在大多数场景下都能提供更好的查询性能和更高的准确率。然而,HNSW的内存消耗相对较高,这是它的一个潜在缺点。<h2 id=5-HNSW的实际应用><a title="5. HNSW的实际应用" class=headerlink href=#5-HNSW的实际应用></a>5. HNSW的实际应用</h2><h3 id=在推荐系统中的应用><a class=headerlink href=#在推荐系统中的应用 title=在推荐系统中的应用></a>在推荐系统中的应用</h3><p>HNSW可以用于快速检索相似用户或物品,提高推荐系统的响应速度和准确性。例如,在音乐推荐中,可以用HNSW快速找到与用户喜好相似的歌曲。<h3 id=在图像检索中的应用><a class=headerlink href=#在图像检索中的应用 title=在图像检索中的应用></a>在图像检索中的应用</h3><p>在大规模图像数据库中,HNSW可以实现快速的相似图像搜索。这在图像搜索引擎、视觉商品搜索等场景中非常有用。<h3 id=在自然语言处理中的应用><a class=headerlink href=#在自然语言处理中的应用 title=在自然语言处理中的应用></a>在自然语言处理中的应用</h3><p>HNSW可以用于词嵌入或句子嵌入的快速检索,支持语义相似度计算、文本分类等任务。<h2 id=6-HNSW的优化和变种><a title="6. HNSW的优化和变种" class=headerlink href=#6-HNSW的优化和变种></a>6. HNSW的优化和变种</h2><h3 id=参数调优技巧><a class=headerlink href=#参数调优技巧 title=参数调优技巧></a>参数调优技巧</h3><ul><li>层数选择:影响搜索速度和内存使用<li>每层连接数:影响搜索准确度和构建时间<li>候选集大小:影响搜索质量和速度的平衡</ul><h3 id=常见的HNSW变种算法介绍><a class=headerlink href=#常见的HNSW变种算法介绍 title=常见的HNSW变种算法介绍></a>常见的HNSW变种算法介绍</h3><ul><li>NSW-G:改进了图的构建方法,提高了搜索效率<li>HCNNG:结合了层次聚类,提高了在某些数据集上的性能</ul><h2 id=7-实现HNSW的挑战与解决方案><a title="7. 实现HNSW的挑战与解决方案" class=headerlink href=#7-实现HNSW的挑战与解决方案></a>7. 实现HNSW的挑战与解决方案</h2><h3 id=大规模数据集的处理><a class=headerlink href=#大规模数据集的处理 title=大规模数据集的处理></a>大规模数据集的处理</h3><ul><li>使用外部存储和分批处理<li>采用压缩技术减少内存占用</ul><h3 id=并行化和分布式实现><a class=headerlink href=#并行化和分布式实现 title=并行化和分布式实现></a>并行化和分布式实现</h3><ul><li>搜索过程的并行化<li>分布式索引构建和查询</ul><h3 id=动态更新和删除操作的处理><a class=headerlink href=#动态更新和删除操作的处理 title=动态更新和删除操作的处理></a>动态更新和删除操作的处理</h3><ul><li>软删除技术<li>定期重建索引</ul><h2 id=8-总结与展望><a title="8. 总结与展望" class=headerlink href=#8-总结与展望></a>8. 总结与展望</h2><p>HNSW算法通过其独特的分层小世界图结构,在保证高准确率的同时实现了对高维向量数据的快速检索。它在推荐系统、图像检索、自然语言处理等多个领域都有广泛应用。<p>未来,向量数据库技术可能会朝着以下方向发展:<ol><li>更高效的压缩和索引技术<li>更好的动态更新支持<li>与深度学习模型的更紧密集成<li>针对特定领域的优化变体</ol><p>随着人工智能和大数据技术的不断发展,HNSW等高效的向量检索算法将在更广阔的应用场景中发挥重要作用。</div><footer class=post-footer><aside aria-label=文章所属专题 class=post-series><span>所属专题</span><a href=/topics/#local-llm>低成本大模型推理</a><p>从本地部署、量化和 KV Cache 参数入手,逐步理解显存占用、GPU Offload 与 MoE 专家缓存。</aside><div class="affiliate-creative affiliate-creative--post-end" data-affiliate-id=tencent-cloud-server><a rel="sponsored noopener" aria-label=腾讯云服务器优惠 href=https://cloud.tencent.com/act/cps/redirect?redirect=6544&cps_key=2e33a1eedb380997d03618b4a5ba6ca7&from=console target=_blank><img alt="腾讯云 AI 焕新云服务器优惠" decoding=async height=241 loading=lazy src=/uploads/affiliate/tencent-cloud-server.webp width=690> </a><span class=affiliate-disclosure>推广</span></div><div class=reward-container><div>请我一杯咖啡吧!</div><button>赞赏</button><div class=post-reward><div><img alt="Nicksxs 微信" src=https://i.loli.net/2020/01/12/NUlWanT31E8LQGx.png><span>微信</span></div><div><img alt="Nicksxs 支付宝" src=https://ooo.0o0.ooo/2016/08/17/57b421e773057.jpg><span>支付宝</span></div></div></div><div class=post-copyright><ul><li class=post-copyright-author><strong>本文作者: </strong>Nicksxs<li class=post-copyright-link><strong>本文链接:</strong> <a title="HNSW 算法原理详解:分层图构建、搜索流程与参数调优" href=https://nicksxs.me/2024/06/23/%E4%BB%8B%E7%BB%8D%E4%B8%80%E4%B8%8BHNSW%E7%AE%97%E6%B3%95/>https://nicksxs.me/2024/06/23/介绍一下HNSW算法/</a><li class=post-copyright-license><strong>版权声明: </strong>本博客所有文章除特别声明外,均采用 <a href=https://creativecommons.org/licenses/by-nc-sa/4.0/ rel=noopener target=_blank><i class="fab fa-fw fa-creative-commons"></i>BY-NC-SA</a> 许可协议。转载请注明出处!</ul></div><div class=post-tags><a href=/tags/LLM/ rel=tag># LLM</a><a href=/tags/%E7%AE%97%E6%B3%95/ rel=tag># 算法</a></div><div class=post-nav><div class=post-nav-item><a title="NX30Pro 刷成 Openwrt-ImmortalWrt 后作为有线中继的配置方法" href=/2024/06/16/NX30Pro-%E5%88%B7%E6%88%90-Openwrt-ImmortalWrt-%E5%90%8E%E4%BD%9C%E4%B8%BA%E6%9C%89%E7%BA%BF%E4%B8%AD%E7%BB%A7%E7%9A%84%E9%85%8D%E7%BD%AE%E6%96%B9%E6%B3%95/ rel=prev><i class="fa fa-angle-left"></i> NX30Pro 刷成 Openwrt-ImmortalWrt 后作为有线中继的配置方法</a></div><div class=post-nav-item><a href=/2024/06/30/%E4%BB%8B%E7%BB%8D%E4%B8%80%E4%B8%8BJava%E7%9A%84BiFunction/ rel=next title=介绍一下Java的BiFunction>介绍一下Java的BiFunction <i class="fa fa-angle-right"></i></a></div></div></footer></article></div><div class=comments id=disqus_thread><noscript>Please enable JavaScript to view the comments powered by Disqus.</noscript></div></div></main><footer class=footer><div class=footer-inner><div class=beian><a href=https://beian.miit.gov.cn/ rel=noopener target=_blank>浙ICP备16002580号-2 </a><img alt src=/uploads/beian.png><a href=https://beian.mps.gov.cn/#/query/webSearch?code=33010602011094 rel=noopener target=_blank>浙公网安备 33010602011094号</a></div><div class=copyright>© <span itemprop=copyrightYear>2026</span><span class=with-love><i class="fa fa-heart"></i> </span><span class=author itemprop=copyrightHolder>Nicksxs</span></div></div></footer><div class="toggle sidebar-toggle" role=button><span class=toggle-line></span><span class=toggle-line></span><span class=toggle-line></span></div><div class=sidebar-dimmer></div><div aria-label=返回顶部 class=back-to-top role=button><i class="fa fa-arrow-up fa-lg"></i><span>0%</span></div><a aria-label="在 GitHub 上关注我" title="在 GitHub 上关注我" class=github-corner href=https://github.com/nicksxs rel=noopener target=_blank><svg viewbox="0 0 250 250" aria-hidden=true height=80 width=80><path d="M0,0 L115,115 L130,115 L142,142 L250,250 L250,0 Z"></path><path d="M128.3,109.0 C113.8,99.7 119.0,89.6 119.0,89.6 C122.0,82.7 120.5,78.6 120.5,78.6 C119.2,72.0 123.4,76.3 123.4,76.3 C127.3,80.9 125.5,87.3 125.5,87.3 C122.9,97.6 130.6,101.9 134.4,103.2" style="transform-origin:130px 106px" class=octo-arm fill=currentColor></path><path d="M115.0,115.0 C114.9,115.1 118.7,116.5 119.8,115.4 L133.7,101.6 C136.9,99.2 139.9,98.4 142.2,98.6 C133.8,88.0 127.5,74.4 143.8,58.0 C148.5,53.4 154.0,51.2 159.7,51.0 C160.3,49.4 163.2,43.6 171.4,40.1 C171.4,40.1 176.1,42.5 178.8,56.2 C183.1,58.6 187.2,61.8 190.9,65.4 C194.5,69.0 197.7,73.2 200.1,77.6 C213.8,80.2 216.3,84.9 216.3,84.9 C212.7,93.1 206.9,96.0 205.4,96.6 C205.1,102.4 203.0,107.8 198.3,112.5 C181.9,128.9 168.3,122.5 157.7,114.1 C157.9,116.9 156.7,120.9 152.7,124.9 L141.0,136.5 C139.8,137.7 141.6,141.9 141.8,141.8 Z" class=octo-body fill=currentColor></path></svg></a><noscript><div class=noscript-warning>Theme NexT works best with JavaScript enabled</div></noscript><script data-cloudflare-page-counter-config type=application/json>{"enable":true,"endpoint":"https://counter.nicksxs.me","site":"nicksxs","local_cache":true,"timeout":5000,"icon":"far fa-eye","item_text":true}</script><script src=/js/cloudflare-page-counter.js></script><script class=next-config data-name=disqus type=application/json>{"enable":true,"shortname":"nicksxs","count":false,"i18n":{"disqus":"disqus"}}</script><script defer src=/js/third-party/comments/disqus.js></script>