Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Last updated: Monday 07 September 2026 @ 20:44:27

构建

  • 取 N/M (M为HNSW图中的节点邻居数,最底层为2M)的点作为上层导航图先进行构建,再将所有 N 点利用上层导航图完成划分分片。
  • 上层导航图先利用聚类算法根据聚集关系进行划分,再通过自搜索方式进行微调划分关系。
    • 自搜索:以该点作为目标进行搜索(efsearch=efs)对得到的 efs 个结果进行投票,每个结果以自己所在的分区进行投票,将目标点移动到票数最多的分区上。
  • 导航图分配点到分片上时,分片同步进行索引构建。对于多分配,则相当于多个分片都接收到了要构建的点,由于分配速度比构建速度快,需要做好缓冲,避免同步阻塞。
    • 分配与多分配:一个点应该分配到哪个分片上,应当由其在导航图上的搜索结果确定,以该点作为目标点在导航图上以 efsearch=efs 进行搜索,对于得到的搜索结果,每个结果根据其所在的分片进行投票,最终将目标点分配到所有票数最高的分片上,若最高票为 1 票,则只分配到最近的分片上。
  • 分片上构建点时构建完整的多层 HNSW 图。

搜索

  • 搜索时根据导航图搜索结果所在的分片来决定哪些分片需要参与搜索,导航图搜索结果中一个分片上的结果点越多,该分片的 efsearch 越大,efsearch= a * EP+b,EP 是该分片的搜索结果个数。
  • 在分片上的图中进行搜索时,以导航图中的结果点作为入口点直接在底层分片的最底层开始搜索。
  • 搜索时负责路由的导航图与分片,分片与分片之间,分片内部都要充分地并行,不要让 query 之间存在同步阻塞。